[wesammikhail]

Basically any NP problem fits that category. Protein folding is one but so are many other problems. But even if the verification itself is hard (EXP problem) that could still work as at least that energy we are putting into the network will eventually produce an answer (less efficiently, granted!) but it is far better than having energy be for literally 0 gain as the produced outcome right now is tossed out as "junk".

[nicky0]

The gain is in the security of the currency. You can argue about how valuable that is, but it is not "literally zero".