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.