According to Stephen Cook on wikipedia, http://en.wikipedia.org/wiki/P_versus_NP_problem ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a ...
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy to test for membership but a lot more difficult to find members, and for others the reverse is true. Here is an elementary ...