I initially took issue with "first asymmetric proof of work", thinking that in practice any NP-complete problem would surely be fine, even if we can’t prove that it can’t be solved quickly. But is it difficult to find NP-complete problems which can't also be quickly approximated? And I suppose it might also be hard to find NP-complete problems in a "Goldilocks zone" of difficulty to make for practical proofs of work, since their complexity increases so sharply.
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.
Approximation doesn't help, since you can require optimal solutions, but yes, it's very difficult to come up with hard instances. After all, you need to know the correct answer, so you can't just randomly generate instances. In addition, SAT solvers are ridiculously good these days.
