[tradedash]

What you just said is the "definition" of NP problems which is why I had it in my question to begin with. Even if genome sequencing is not a good problem for mining. There are plenty of other scientific problems that are. Yet mining today is not tackling any of them :/

[ewjordan]

The miner's identity (more or less) has to be one of the inputs to the problem, so that everyone is actually working on a different problem and you can't "steal" a block just by broadcasting another person's solution faster and wider.

Maybe there could be useful problems with this property, but it's not trivial to find them.