Theory of computation. (Q2492014): Difference between revisions

This book represents the lecture notes of Dexter Kozen for the first-year graduate students in computer science at Cornell University. The book contains 41 primary lectures and 10 supplementary lectures covering more specialized and advanced topics. There are also 12 homework sets and several miscellaneous homework exercises of varying level of difficulty, many with hints and complete solutions. In Lectures 1 and 2 the complexity of computation is defined by means of Turing machines. So the time and space complexity classes are defined and the relations between them (Savitch's Theorem) given. Deterministic and nondeterministic separation results are presented in Lecture 3. The Immerman-Szelepcseny Theorem about the property of the nondeterministic space complexity class, that it is closed under complement, is the subject of Lecture 4. Lecture 5 presents logspace computability, and Lecture 6 the Circuit Value Problem. Here, the Cook-Levin Theorem and, supplementary, the Knaster-Tarski Theorem are presented. In Lecture 7 alternating Turing machines and complexity results for alternating complexity classes are proved. Problems complete for PSPACE, the quantified Boolean formula problem, the two-person perfect information game and the generalized geography game are the subjects of Lecture 8. The polynomial-time hierarchy is presented in Lectures 9 and 10. For this hierarchy the generic complete problem is defined in terms of oracle Turing machines. An introduction to parallel computation from a complexity point of view is given in Lecture 11. The first model of parallel complexity defined is the uniform family of circuits, and the most popular parallel complexity class defined in terms of uniform circuits is NC (Nick's class). The relation of NC to Time Space Classes is presented in Lecture 12. In Lecture 13 probabilistic Turing machines and probabilistic complexity classes are defined. Also the random polynomial time class, RP, is defined. The relation between bounded probabilistic polynomial time and classes from the polynomial time hierarchy (due to Sipser) is the subject of Lecture 14. Three supplementary lectures are presented here: Chinese Remainder Theorem, Complexity of Primality Testing and Berlekamp's Algorithm for factoring a given univariate polynomial over a finite field of large characteristic. The next few lectures (15, 16 and 17) present a model of computational involving interactive protocols between two agents used in cryptography and in message authentication. The complexity class IP (polynomial-time interactive protocols) and the interactive proofs are defined, and the relations between PSPACE and IP are proved. In Lectures 18, 19 and 20 some complexity results about the relationship between interactive protocols and approximation algorithms are presented. The model used for this purpose is PCP (probabilistic checkable proofs). For the next lectures (21--25) some notions about logic are presented in a supplementary lecture. The complexity of the first-order theories in terms of Ehrenfeucht-Fraissé games is the subject of the Lecture 21, and the decidability of the first-order theory of the reals with addition and multiplication is the subject of Lecture 22. It is shown that the weaker theory of real addition \({\text{Th}({\mathbb{R}},+,\leq)}\), the first-order theory of the real numbers with addition + and order \(\leq\) , is complete for the complexity class \({\text{STA}(\ast,2^{O(n)},n)}\). In Lecture 23 it is shown that the theory of real addition \({\text{Th}({\mathbb{R}},+,\leq)}\) is hard for this complexity class \({\text{STA}(\ast,2^{O(n)},n)}\). In Lecture 24 it is described how to obtain the lower bound for the theory of integer addition, \({\text{Th}(\mathbb{Z,}+,\leq)}\), the Presburger arithmetic. The monadic second-order theory of successor (S1S) is the subject of Lecture 25. The decidability of S1S is proved using automata on infinite strings. In Lectures 26 and 27 three types of automata on infinite strings are defined: Büchi, Rabin and Muller, and a construction due to Safra for the determination of Büchi automata is presented. The subject of Lecture 28 is a fundamental question, probably the most important one in complexity theory: the P = NP question. Some results due to Fairly, Baker, Gill and Solovay are presented for understanding this question and similar questions regarding containment and separation of complexity classes. Related to the P = NP question, the subject of Lecture 29 is the nonexistence of sparse complete sets. In two supplementary Lectures, F and G, the author studies some interesting reducibility relations involving randomness and counting and proves two results in structural complexity theory: the first is the result of Valiant and Vazirani that Boolean satisfiability is not easier for formulas that are guaranteed to have at most one solution than for arbitrary formulas, and the second is a result of Toda that the ability to count solutions to instances of NP-complete problems allows one to compute any set in the polynomial-time hierarchy. In Lectures 30 and 31 lower bounds for families of Boolean circuits of constant depth and their application to relativized complexity are presented. For this purpose the complexity class AC\(^0\) of Boolean functions is introduced that can be computed by a family of constant-depth, polynomial-size circuits of unbounded indegree. It is shown that a sufficiently strong superpolynomial lower bound on the size of constant-depth circuits for PARITY implies the existence of an oracle separating PSPACE (Furst, Saxe and Sipser). Stronger bounds achieving separation, the Hastad switching lemma, is presented in the Supplementary Lecture H. In the Supplementary Lecture I two tail bounds are presented: Markov bound and Chebyshev bound, that are used in probabilistic analysis. For better understanding the power and the limitations of complexity theory in Lecture 32 some examples are presented. An introduction to classical recursive function theory is presented in Lectures 33 and 34. A formalization of the abstract notion of complexity measures, due to Blum, is the subject of the Supplementary Lecture J. In Lecture 35, analogous to the polynomial time hierarchy, a hierarchy of classes above the recursively enumerable sets, the arithmetic hierarchy, is defined. Some natural problems complete for the third level of the arithmetic hierarchy are presented in Lecture 36. Post's problem regarding r.e. m-degrees and the result of Friedberg and Muchnik are the subjects in Lectures 37 and 38. The analytic hierarchy, related to second-order number theory, and Kleene's Theorem, which is related to the structure of arithmetic, are the subjects of Lectures 39 and 40. In the last lecture, Lecture 41, an example of a real application from computer science for the theoretical notions from lectures 39 and 40 is presented: proving fair termination of concurrent programs. After the 12 homeworks and some solutions and hints for selected exercises, there is a bibliography of 127 titles. The book contains a very useful list of notations and abbreviations and an index.