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.