CMSC 38500-1: Computability and Complexity Theory

Course description. See also the previous version of this course (some changes are anticipated).

Spring 2014: Tuesday, Thursday 1:30pm-2:50pm (Ry 277)

Office hours: by appointment.
Homeworks. There will be three homework assignments. You are encouraged to work together on solving homework problems. All students must turn in their own write-up of the solutions. If you work with other people, you must put their names clearly on the write-up.

Progress and references.
- First week: Primitive recursive functions [Cutland, Chapters 2.1-2.4; Mendelson, Chapter 3.3]. The Ackermann function [Cut., Ch.2, Example 5.5], see also Wikipedia article. The latter contains our computation of A(4,3) as well as a few other values. The Ackermann function is not primitive recursive. Lower envelopes and Davenport-Schinzel sequences [3, Section 1.1]. Bounds on the length of DS-sequences (without proof) [3, Section 2.2]. Goedel numbers are commonly used for encoding/decoding sequences of finite but unlimited length and consisting of objects of quite different nature, like first-order formulae [Mend., Ch. 3.4] or Turing machines [Mend., Prop. 5.4]. Our student John Loeber has created a simple script that computes the Goedel encoding of plain English text; it can be downloaded here. Recursive functions [Cut., Ch. 3.2 and 2.5; Mend., Ch. 3.3].
- Second week: Turing machines [Mend., Ch. 5.1; Cut., Ch. 3.4]. Unlimited register machines [Cut., Ch. 1 and 2]. Every recursive function is URM-computable [Cut., Theorem 3.2.2]. Markov Normal Algorithms [Mend., Ch. 5.5; Cut., Ch. 3.5]. For a lovely discussion of Kolmogorov-Uspensky machines see [4]. Church-Turing Thesis [Cut., Ch. 3.7]. Decidable problems, recursive and recursively enumerable sets [Cut., Ch. 6 and 7]. Enumerations $\phi_e$ and $W_e$ of recursive functions and r.e. sets [Cut., Ch. 4.2]. Halting problem is undecidable [Cut., Thm 6.1.3]. Many-one reducibility [Cut., Ch. 9.1]. s-m-n Theorem [Cut., Ch. 4.4]. Rice's theorem [Cut., Thm 6.1.7].
- Third week: Rice's theorem (cntd). Relative (oracle) computations: [Cut., Ch. 9.4]. Turing equivalence and degrees [Cut., Ch. 9.5]. Post's problem: [Cut., Problem 9.5.11]. Simple sets [Cut., Ch. 7.4]. Creative sets [Cut., Ch. 7.3]. Creative sets are not simple [Cut., Thm 7.3.11]. Effective (recursive) operators and their simple properties: [Cut., Ch. 10.1]. Myhill-Shepherdson theorem [Cut., Ch. 10.2]. Kleene's fixed point theorem (aka the First Recursion Theorem) [Cut., Ch. 10.3].
- Fourth week (short): Kleene's fixed point theorem (cntd.) First-order logic [Mend., Ch. 2; Cut., Ch. 8.1]. Peano Arithmetic [Mend., Ch. 3.1].
- Fifth week: Defining new function symbols [Mend., Ch. 2.9]. Recursive functions are definable (representable) in PA [Mend., Proposition 3.24]. $\omega$-consistency [Cut., Ch. 8.3; Mend., Ch, 3.5]. Th(PA) is undecidable [Cut., Ch. 8.3; Mend., Ch. 3.6]. There are a few variations on the topic "Goedel Incompleteness Theorem via recursion theory". The simple version we did in the class more or less corresponds to [Mend., Prop. 3.47 and Corollary 3.48]. I recommend to check out also [Cut., Theorem 8.2.4] in which the Incompleteness Theorem is handled without any technical work on definability/arithmetization whatsoever. It also provides an alternate proof of undecidability of pure first-order calculus. [5] is an excellent survey on decidable theories. Quantifier elimination technique [Mend., page 110 (Ch. 2.12)]. For Presburger Arithmetic see the Wikipedia article which also gives a reference to the simple QE proof we did in class. Another beautiful proof based on totally different ideas can be found in [5, Sct. 3.4]. Among other things, it also conclusively demonstrates that second-order systems sometimes are useful. Robinson's Arithmetic, called RR in [Mend., Ch. 3.4]. Deduction Theorem [Mend., Ch. 2.4, Prop. 2.5]. Pure first-order calculus is undecidable [Mend., Ch. 3.6, Cor. 3.52]. Hilbert's Tenth problem [Cut., Ch. 6.3 and 6.6.]. Word problem in groups [Cat., Ch. 6.2]; for more information see [6]. Asymptotic extremal combinatorics is undecidable [7]; for the context see [8]. Our basic text on Kolmogorov Complexity is [9], but many simple things we will be doing next week are covered already in [10, Chapter 6.4].
- Sixth week: Invariance Theorem [10, Thm. 6.27]. Incompressible strings [10, Def. 6.28, Thm. 6.29-6.32]. Conditional Kolmogorov complexity [9, Def. 2.1.1 and 2.1.2]. Algorithmic Prefix Complexity (just mentioned) [9, Ch. 3]. Classical information theory [9, Ch. 1.11]. Conditional Kolmogorov complexity behaves as expected [9, Thm. 2.8.2]. Random infinite sequences [9, Ch. 2.5.2].
- Seventh week: Random infinite sequences (cntd.). Incompressibility of finite prefixes implies randomness (without proof) [9, Thm. 2.5.5]. For a (highly) informal introduction into the complexity block see [12]. Machine-independent complexity, Blum's axioms [Cut., Ch. 12.1]. Speed-up Theorem (without proof) [Cut., Thm. 12.2.1]. Gap Theorem (without proof) [Cut., Thm. 12.3.1]. Complexity classes, DTIME [10, Ch. 7.1; 11, Ch. 1.6]. Discussion on worst-case analysis, asympotics assumptions etc. [12; 13; 10, Ch. 7.2; 11, Ch. 1.6]. Time Hierarchy Theorem [10, Thm. 9.10; 11, Thm. 3.1]. Space Hierarchy Theorem (without proof) [10, Thm. 9.3]. Relations between time and space [11, Thm. 4.2]. Complexity of decidable logical theories [5, Ch. 4]. Class P [11, Ch. 1.6]. Strong Church-Turing thesis [11, Ch. 1.6]. Karp reductions [11, Ch. 2.2].
- Eighth week: Class NP [11, Ch. 2.1]. NTIME and equivalence of the two definitions [11, Ch. 2.1.1]. Universal NP-complete problem [11, Thm. 2.9]. Cook-Levin Theorem [10, Thm. 7.37]. 3-SAT is NP-complete [10, , Cor. 7.42]. Examples of NP-complete problems [14; 10, Ch. 7.5; 11, Ch. 2.4], see also Wikipedia link. Bounded version of Hilbert's tenth problem is NP-complete [14]. Solvability of quadratic equations in free groups is NP-complete [15].
- Ninth week: Examples of NP-complete problems (cntd). TQBF and its PSPACE-completeness [11, Thm. 4.13]. Savitch's theorem [11, Ch. 4.2.1]. Immerman-Szelepcsenyi theorem (without proof) [11, Thm. 4.20]. Other complete problems for PSPACE and EXPTIME with references can be found here and here. Ladner's theorem (without proof) [11, Ch. 3.3]. Limits of diagonalization: Baker-Gill-Solovay Theorem [11, Thm. 3.7]. Polynomial-time hierarchy [11, Ch. 5]. Randomized computations, definitions [11, Ch. 7.1 and 7.3]. BPP is strange [11, Ch. 7.5.3]. Sipser-Gacs Theorem [11, Thm. 7.15].
- Tenth week (short): Sipser-Gacs Theorem (cntd). Error-reduction [11, Thm. 7.10]. Interactive proofs: an overview; for missing details see [11, Ch. 8].

Literature.
1. N. J. Cutland, Computability, Cambridge University Press, 1980.
2. E. Mendelson, Introduction to Mathematical Logic, fifth edition, CRC Press, 2009.
3. M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
4. Y. Gurevich, On Kolmogorov Machines And Related Issues, Bulletin of European Assoc. for Theor. Comp. Science, 35, 1988, pages 71-82.
5. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
6. S. I. Adian, G. S. Makanin, Studies in algorithmic questions of algebra, in Algebra, mathematical logic, number theory, topology, Collection of survey articles. 1. On the occasion of the 50th anniversary of the founding of the Institute, Trudy Mat. Inst. Steklov., 168, 1984, 197-217.
7. H. Hatami, S. Norin, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc., 24 (2011), 547-565.
8. A. Razborov, What is a Flag Algebra?, Notices of the AMS, 60(10): 1324-1327, 2013.
9. M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, third edition, Springer, 2008.
10. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
11. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
12. A. Razborov, Foundations of computational complexity theory, Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, No. 321, 2005, pages 186-202.
13. S. Cook, Computational Complexity of Higher Type Functions, Proceedings of 1990 Intern. Congress of Mathematicians, Kyoto, Japan, Springer, 1991, 55-69.
14. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
15. K. Manders, L. Adleman, NP-complete decision problems for quadratic polynomials, Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, pages 23-29, 1976.
16. O. Kharlampovich, I.G. Lysenok, A.G. Myasnikov, N.W.M. Touikan, The Solvability Problem for Quadratic Equations over Free Groups is NP-Complete , Theory of Computing Systems, vol. 47, No 1, pages 250-258, 2010.