No they aren't.

For a PoW to be valuable it needs to be cheap to verify. Hard problems usually aren't.

What? Any NP-complete problem is "cheap" to verify vs. to solve. You're telling me there are no economically valuable NP-complete problems?

If there are, why has no one built a coin around it unstead of using untold watts to calculate hashes?

They did, like protein folding.

Part of it is that if its going to be a currency, its not particularly appealing that some group gets arbitrary benefits from the act of mining, for free. The government has the power to force such a currency on us, but otherwise, unless the economically valuable activity is globally valuable, its a difficult proposition to justify.

umm, generating a block whose hash starts with N consecutive zeroes (e.g. 000000009A8C3...) seems to be exactly that - an NP hard problem that's trivial to verify in polynomial time.

yes, but it's not useful in someway outside of the blockchain, which was the thrust of GP's argument.

Isn't the entire NP class hard to solve, cheap to verify? Im sure some economically valuable problem can boil down to an NP problem...

Most solutions to NP problems are cheap to verify.

What you want are "moderately hard functions": functions that are neither easy nor excessively hard.

If a proof of work solution is economically valuable to solve, the hashrate will just increase to the point where it's just marginally profitable again.