Description

Chapter 1 The Gödel Phenomena in Mathematics: A Modern View Avi Wigderson Herbert Maass Professor School of Mathematics Institute for Advanced Study Princeton, New Jersey, USA 1.1 Introduction What are

Information

Category:
## Music & Video

Publish on:

Views: 60 | Pages: 20

Extension: PDF | Download: 0

Share

Transcript

Chapter 1 The Gödel Phenomena in Mathematics: A Modern View Avi Wigderson Herbert Maass Professor School of Mathematics Institute for Advanced Study Princeton, New Jersey, USA 1.1 Introduction What are the limits of mathematical knowledge? The purpose of this chapter is to introduce the main concepts from computational complexity theory that are relevant to algorithmic accessibility of mathematical understanding. In particular, I ll discuss the P versus N P problem, its possible impact on research in mathematics, and how interested Gödel himself was in this computational viewpoint. Much of the technical material will be necessarily sketchy. The interested reader is referred to the standard texts on computational complexity theory, primarily [5, 25, 43, 61] Overview Hilbert believed that all mathematical truths are knowable and set the threshold for mathematical knowledge at the ability to devise a mechanical procedure. This dream was shattered by Gödel and Turing. Gödel s incompleteness theorem exhibited true statements that can never be proved. Turing formalized Hilbert s notion of computation and of finite algorithms (thereby initiating the computer revolution) and proved that some problems are undecidable they have no such algorithms. While the first examples of such unknowables seemed somewhat unnatural, more and more natural examples of unprovable or undecidable problems were found in different areas of mathematics. The independence of the continuum hypothesis and the undecidability of Diophantine equations are famous 1 Gödel Book Wigderson - rev early examples. This became known as the Gödel phenomena, and its effect on the practice of mathematics has been debated since. Many argued that while some of the inaccessible truths above are natural, they are far from what is really of interest to most working mathematicians. Indeed, it would seem that in the seventy-five years since the incompleteness theorem, mathematics has continued thriving, with remarkable achievements such as the recent settlement of Fermat s last theorem by Wiles and the Poincaré conjecture by Perelman. So, are there interesting mathematical truths that are unknowable? The main point of this chapter is that when knowability is interpreted by modern standards, namely via computational complexity, the Gödel phenomena are very much with us. We argue that to understand a mathematical structure, having a decision procedure is but a first approximation, and that a real understanding requires an efficient algorithm. Remarkably, Gödel was the first to propose this modern view, in a letter to von Neumann in 1956, which was discovered only in the 1990s. Meanwhile, from the mid-1960s on, the field of theoretical computer science has made formal Gödel s challenge and has created a theory that enables quantification of the difficulty of computational problems. In particular, a reasonable way to capture knowable problems (which we can efficiently solve) is the class P, and a reasonable way to capture interesting problems (which we would like to solve) is the class N P. Moreover, assuming the widely believed P = N P conjecture, the class N P-complete captures interesting unknowable problems. In this chapter, I define these complexity classes, explain their intuitive meaning, and show how Gödel foresaw some of these definitions and connections. I relate computational difficulty to mathematical difficulty and argue how such notions, developed in computational complexity, may explain the difficulty mathematicians have in accessing structural, non-computational information. I also survey proof complexity the study of lengths of proofs in different proof systems. Finally, I point out that this modern view of the limits of mathematical knowledge is adopted by a growing number of mathematicians, working on a diverse set of interesting structures in different areas of mathematics. This activity increases interaction with computer scientists and benefits both fields. Results are of two types, as in standard computer science problems. On the one hand, there is a growing effort to go beyond characterizations of mathematical structures, and attempts are made to provide efficient recognition algorithms. On the other, there is a growing number of N P-completeness results, providing the stamp of difficulty for achieving useful characterizations and algorithms. This second phenomenon, now ubiquitous in science and mathematics, may perhaps better capture Gödel s legacy on what is unknowable in mathematics Decision Problems and Finite Algorithms Which mathematical structures can we hope to understand? Let us focus on the most basic mathematical task of classification. We are interested in a particular class of objects and a particular property. We seek to understand which of the objects have the property and which do not. Let us consider the following Gödel Book Wigderson - rev examples: (1) Which valid sentences in first-order predicate logic are provable? (2) Which Diophantine equations have solutions? (3) Which knots are unknotted? (4) Which elementary statements about the reals are true? It is clear that each object from the families above has a finite representation. Hilbert s challenge was about the possibility to find, for each such family, a finite procedure that would solve the decision problem in finite time for every object in the family. In his seminal paper [63, 64], Turing formulated the Turing machine, a mathematical definition of an algorithm, capturing such finite mechanical procedures. This allowed a mathematical study of Hilbert s challenge. Hilbert s Entscheidungsproblem problem (1) above was the first to be resolved, in the same paper by Turing. Turing showed that problem (1) is undecidable, namely there is no algorithm that distinguishes provable from unprovable statements of first-order predicate logic. Hilbert s 10th problem problem (2) above was shown to be undecidable as well, in a series of works by Davis, Putnam, Robinson, and Matiasevich [41]. Again, no algorithm can distinguish solvable from unsolvable Diophantine equations. The crucial ingredient in those (and all other) undecidability results is showing that each of these mathematical structures can encode computation. This is known today to hold for many different structures in algebra, topology, geometry, analysis, logic, and more, even though a priori the structures studied seem to be completely unrelated to computation. It is as though much of contemporary work in mathematics is pursuing, unwittingly and subconsciously, an agenda with essential computational components. I shall return to refined versions of this idea later. The notion of a decision procedure as a minimal requirement for understanding of a mathematical problem has also led to direct positive results. It suggests that we look for a decision procedure as a means, or as a first step for understanding a problem. For problems (3) and (4) above this was successful. Haken [30] showed how knots can be so understood, with his decision procedure for problem (3), and Tarski [62] showed that real-closed fields can be understood with a decision procedure for problem (4). Naturally, significant mathematical, structural understanding was needed to develop these algorithms. Haken developed the theory of normal surfaces and Tarski invented quantifier elimination for their algorithms, both cornerstones of the respective fields. This reveals only the obvious: mathematical and algorithmic understanding are related and often go hand in hand. There are many ancient examples. The earliest is probably Euclid s greatest common divisor (GCD) algorithm. Abel s proof that roots of real polynomials of degree at least 5 have no formula with radicals is the first impossibility result (of certain classes of algorithms). Of course, Newton s algorithm for approximating such roots is a satisfactory Gödel Book Wigderson - rev practical alternative. What was true in previous centuries is truer in this one: the language of algorithms is slowly becoming competitive with the language of equations and formulas (which are special cases of algorithms) for explaining complex mathematical structures. Back to our four problems. The undecidability of problems (1) and (2) certainly suggests that these structures cannot be mathematically understood in general. This led researchers to consider special cases of them that are decidable. But does decidability for example, that of problems (3) and (4) mean that we completely understand these structures? Far from it. Both algorithms are extremely complex and time consuming. Even structurally speaking, there are no known complete knot invariants or characterizations of real varieties. How can one explain such mathematical difficulties for decidable problems? It is natural to go beyond decidability and try to quantify the level of understanding. We will use a computational yardstick for it. We argue that better mathematical understanding goes hand in hand with better algorithms for obtaining that understanding from the given structures. To formalize this, we will introduce the computational terms that are central to the theory of computational complexity. There is no better way to start this than with Gödel s letter to von Neumann. 1.2 Gödel s Letter to von Neumann In Gödel s letter, which I include below in its entirety for completeness, complexity is discussed only in the second paragraph it is remarkable how much this paragraph contains! It defines asymptotic and worst-case time complexity, suggests the study of the satisfiability problem, discusses the mathematical significance of having a fast algorithm for it, and even speculates on the possibility of the existence of such an algorithm. In the section that follows the letter, I identify the letter s contributions and insights in modern language The Letter First, a bit on the context. The letter was written when von Neumann was in the hospital, already terminally ill with cancer (he died a year later). It was written in German, and here we reproduce a translation. The surveys by Sipser [60] and Hartmanis [31] provide the original letter, as well as more details on the translation. As far as we know, the discussion Gödel was trying to initiate never continued. Moreover, we have no evidence of Gödel s thinking more about the subject. Again, we will refer later only to the second paragraph, which addresses the computational complexity issue. Princeton, 20 March 1956 Dear Mr. von Neumann: Gödel Book Wigderson - rev With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery. Since you now, as I hear, are feeling stronger, 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) = max F ψ(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 φ(n) k n 2 ), 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 (apart from the postulation of axioms) 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 1.) 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 2.) after all φ(n) k n (or φ(n) k n 2 ) 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. Gödel Book Wigderson - rev I do not know if you have heard that Post s problem, whether there are degrees of unsolvability among problems of the form ( y)φ(y, x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear. I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife, Sincerely yours, Kurt Gödel P.S. I heartily congratulate you on the award that the American government has given to you Time Complexity and Gödel s Foresight In this section, I go through the main ingredients of Gödel s letter, most of which were independently 1 identified and developed in the evolution of computational complexity in the 1960s and 1970s. These include the basic model, input representation, (asymptotic, worst-case) time complexity, 2 brute-force algorithms and the possibility of beating them, proving lower bounds, and last but not least, Gödel s choice of a focus problem and its significance. I comment on the remarkable foresight of some of Gödel s choices. When introducing some of these notions, I use common, modern notation. Computability vs. complexity: All problems we will discuss here are computable that is, they have a finite algorithm. Gödel states that for his problem, one can...easily construct a Turing machine. We take for granted that the given problem is decidable and ask for the complexity of the best or optimal algorithm. Gödel is the first on record to suggest shifting focus from computability to complexity. 1 Recall that the letter was discovered only in the 1990s. 2 I shall focus on time as the primary resource of algorithms when studying their efficiency. Other resources, such as memory, parallelism, and more, are studied in computational complexity, but I will not treat them here. Gödel Book Wigderson - rev The model: Gödel s computational model of choice is the Turing machine. Time will be measured as the number of elementary steps on a Turing machine. We note that this is a nontrivial choice for a discussion of time complexity back in The Church-Turing thesis of the equivalence of all feasible computational models was around, and all known algorithmic models were known to simulate each other. However, that thesis did not include time bounds, and it seems that Gödel takes for granted (or knows) that all known models can simulate each other efficiently (something that is now well established). The problem: Gödel focuses on one problem to define complexity, a finite version of the Entscheidungsproblem, in which the task is to determine if a formula F has a proof of length n. This is by no means an arbitrary choice, and Gödel is well aware of it, as will be discussed below. Put differently, Gödel s problem asks if we can satisfy a first-order logic verifier that F is provable using only n symbols. We shall later meet its cousin, the problem SAT (abbreviating SATisfyability ), in which the task is to determine if a propositional formula has a satisfying assignment. It is not hard to see that SAT captures Gödel s problem, 3 and so we will call it SAT. Input representation: Every finite object (formulas, integers, graphs, etc.) can be represented as a binary string. We let I stand for the set of all finite binary strings. Let f be a decision problem ( Yes-or-No question in Gödel s letter), like those in Section Then f : I {0, 1} is what we are trying to compute. Thus, we consider Turing machines that for every input x halt with the answer f(x). In Gödel s problem the input is the pair (F, n), and the task is computing whether the first-order formula F has a proof of length at most n. Input length: This is always taken in computational complexity to be the binary length of the input. Clearly Gödel makes the same choice: when he talks about the complexity of testing primality of an integer N, he takes the input length to be log N, the number of bits needed to describe N. Of course, finite objects may have many representations, which differ in length, and one must pick reasonable encodings 4. Time complexity: Complexity is measured as a function of input length. Adapting Gödel s notation, we fix any Turing machine M computing f. We let φ(n) denote the maximum, 5 over all inputs x of length n, of the number of steps M takes when computing f(x). We then consider the 3 Simply assign propositional variables to the n possible proof symbols, and encode the verification process so that indeed they form a proof of F as a Boolean formula. 4 For example, in Gödel s problem it is possible to encode the input using F + log n bits, where F is the encoding length (in bits) of the given first-order formula. However, as we will later see, it is more natural to take it to be F + n, allowing for n variables to encode the possible values of the potential proof symbols. For this problem Gödel indeed measures complexity as a function of n. 5 This worst-case analysis is the most common in complexity theory, though of course other measures are important and well studied too. In particular, average-case analysis (typical Gödel Book Wigderson - rev growth of φ(n) for the optimal machine 6 M. It is quite remarkable that Gödel selects both the asymptotic viewpoint and worst-case complexity neither is an obvious choice but both proved extremely fruitful in the development of computational complexity. Brute-force algorithms: All problems mentioned by Gödel SAT, primality testing, and computing quadratic residue have what Gödel calls trial and error and simple exhaustive search algorithms. All these problems happen to be in the class N P, and these obvious trivial algorithms require exponential time (in the input length). Efficient algorithms: Gödel specifically suggests that time complexity 7 O(n) or O(n 2 ) is efficient (or tractable) enough for practical purposes. This did not change for fifty years, despite enormous changes in computer speed, and is a gold standard of efficiency. I ll try to explain why computational complexity theory chose to call (any) polynomial-time algorithms efficient and the class P to include all problems with such algorithms. The complexity of SAT : Gödel is completely aware of what it would mean if

Related Search

The role of precision journalism in modern coThe Relationship Between Ancient CivilisationHistory of the Balkans in the Late Middle AgeThe development of the Italian novel from itsThe modern history of international relationsMedieval and Early Modern History of the GermCultural Intermediaries In The Early Modern MArtisan Workshop practice in the Early ModernHistory of the Modern Middle EastTribalism in the Modern Middle East

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks