NP and NP completeness
Sanjeev Arora, Boaz Barak · Computational Complexity · 2009
[if φ( n ) ≈ Kn 2 ] then this would have consequences of the greatest magnitude. That is to say, it would clearly indicate that, despite the unsolvability of the [Hilbert] Entscheidungsproblem, the mental effort of the mathematician in the case of the yes-or-no questions would be completely replaced by machines. … [this] seems to me, however, within the realm of possibility. – Kurt Gödel in a letter to John von Neumann, 1956 I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know. – Jack Edmonds, 1966 In this paper we give theorems that suggest, but do not imply, that these problems, as well as many others, will remain intractable perpetually. – Richard Karp, 1972 If you have ever attempted a crossword puzzle, you know that it is much harder to solve it from scratch than to verify a solution provided by someone else. Likewise, solving a math homework problem by yourself is usually much harder than reading and understanding a solution provided by your instructor. The usual explanation for this difference of effort is that finding a solution to a crossword puzzle, or a math problem, requires creative effort . Verifying a solution is much easier since somebody else has already done the creative part.