The http://www.truthcoin.info/blog/pow-cheapest link given above explains why you can incentivise useful processing but it won't stop the 'waste' issue.

You also have the problem of regulating the difficulty if you want consistent rewards. Non-pure math problems aren't going to allow that.