For most cryptocoins, you want a proof-of-work to be: (1) easy for a computer to verify, (2) hard for a computer to perform, (3) impossible to predict for a given 'block' and (4) decentralized and untrusted.
If it's a novel scientific problem it won't be all of these. An interesting exception is prime numbers. Primecoin [1] has a useful proof-of-work: it finds Cunningham chains of primes.
If you don't like the energy consumed by a proof of work, you should probably use something else like proof of stake. Any clever idea to try and steer the computational power to SETI@home or protein folding won't have the critical qualities of most cryptocoins.
You can verify that some fold achieves some energy state. What you cannot efficiently verify is that it's the best possible fold, achieving the global minimum energy.
I spoke briefly with Vijay Pande about this in 2011. Folding does have a lot of the right properties for a good proof-of-work system, the main exception being that the solution must be unique to the input. It may be possible to achieve this by embedding information into sets of constraints, as long as any particular set of constraints can be shown to be isoenergetic. Or perhaps by expanding the problem by adding more atoms in a way that embeds information about the inputs. Also, the solutions would be quite large. But I think he was more interested with my experience writing molecular dynamics code than blockchain, and rescinded the RA offer after this conversation, so I haven’t thought about it much since then.
Reconsidering (briefly) now, I think it can be done.
There's no points for partial credit. It cannot be decentralized, untrusted and unpredictable. If anything other than an automaton produces the PoW inputs, it's at least centralized and we must trust that no one is cheating the PoW.
No points for partial credit?? Well... if you believe that, then that makes Bitcoin suspect as well as its consensus mechanism is essentially already broken by the practical concentration of mining power in a single country with an authoritarian central government.
EDIT: Anyone using an online wallet is already compromising trustlessness. Heck, using common software packages that you didn’t personally inspect is also compromising trustlessness. But does this matter in practicality? Yes (such online wallets and even sometimes soft wallets have been compromised or have lost coins occasionally), but not enough to necessarily get rid of all of the utility of cryptocurrency.
Instead of PoS there are FBA (federated byzantine agreement) chains who are older than PoS thus better tested and arguably without any of the flaws PoS has.
PoS is really a step backward and not the real successor to PoW.
If it's a novel scientific problem it won't be all of these. An interesting exception is prime numbers. Primecoin [1] has a useful proof-of-work: it finds Cunningham chains of primes.
If you don't like the energy consumed by a proof of work, you should probably use something else like proof of stake. Any clever idea to try and steer the computational power to SETI@home or protein folding won't have the critical qualities of most cryptocoins.
[1] https://en.wikipedia.org/wiki/Primecoin