Also, they must be a lottery, in that it's lots of "easy" problems that have a small chance. Otherwise it weakens the "50% attack" by meaning that someone with the most computing power can efficiently "hard" problem much more reliably, rather than the their percentage of the total computing power.
Cryptographic hashes have the unique property that their difficulty is quite predictable, which is an absolute necessity for PoW based voting systems (like Bitcoin). I don't believe there are any known scientific computation problems that have the same desirable PoW properties as a cryptographic hash algorithm.