8
votes
3answers
794 views

P vs. NP resistant problems

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 ...
13
votes
2answers
821 views

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 ...