“The Gödel Letter”, 2009-04-02 (; backlinks; similar):
[Copy of a famous letter by logician Kurt Gödel to mathematician John von Neumann, 1956-03-20, posted by Dick Lipton & Ken Regan because they regard it as the origin of the field of computational complexity, which has had so much practical and theoretical impact on computer science, mathematics, and philosophy by drawing attention to the question of not, ‘what is the algorithm to an answer a question?’, but, ’how much work has to be done to actually calculate said answer?’, which turns out to be an extremely rich and difficult question often of more interest than the first question.]
…I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(F,n). The question is how fast φ(n) grows for an optimal machine.
One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ~ k ⋅ n (or even ~ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning ‘Yes-or-No’ questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem.
Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem and after all φ(n) ~ k ⋅ n (or ~ k ⋅ n2) only means that the number of steps as opposed to trial and error can be reduced from n to log n (or (log N)2). However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.
View External Link: