Problems where it is easy to know whether an answer is correct but hard to get to that answer

The canonical example of this kind of problem is public-private key cryptography where it’s very simple to see if a private key is correct because multiplying it with a public key gives an easily testable value (Need to actually understand how this works.) However figuring out the key from the value would take an obscenely long time to compute.

Systems that obey physics generally have this property - this is why it was possible to make fold it. It’s hard to know how a protein will fold, but you can check whether it is folded correctly just by asking “does this obey physics?”

This concept partially comes from Reinventing Discovery which says that successful collaborations tend to have a gap where it is hard to come up with a solution and easy to recognize a solution as good.


Web URL for this note

Comment on this note