Wouldn't any NP-complete problem serve just as well (http://en.wikipedia.org/wiki/NP-complete)? I think the hashing target thing we currently use is NP-complete, right? So in theory any other NP-complete problem can be transformed in polynomial time into bitcoin generation.