For Proof-of-Work applications, at least in blockchains, you need puzzles that * can be pseudo randomly generated from a seed (usually the hash of a partial bl

For Proof-of-Work applications, at least in blockchains, you need puzzles that * can be pseudo randomly generated from a seed (usually the hash of a partial blockchain header) * have a known optimal solution method with a (nearly) constant running time that's at most about one second (for progress freeness this should be a small fraction of the target block time) NP-hard problems rarely satisfy both these constraints. Finding fixed length cycles in random (bipartite) graphs with billions of edges does.