Someone should make a coin whose proof of work involves solving difficult (but verifiable) problems that are in NP, that are frequently used in commerce.

This would provide a more direct incentive for researchers to make these algorithms faster, and would therefore provide a tangible benefit to society.