CMSC 38500-1: Computability and Complexity Theory

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

Winter 2012: 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 (short): 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.
- Second week: The Ackermann function is not primitive recursive. Lower envelopes and Davenport-Schinzel sequences [3, Section 1.1]. Upper bounds on the length of DS-sequences of order 3 [3, Section 2.2]. Recursive functions [Cut., Ch. 3.2 and 2.5; Mend., Ch. 3.3]. Turing machines [Mend., Ch. 5.1; Cut., Ch. 3.4].
- Third week: 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]. 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].
- Fourth week: Rice's theorem [Cut., Thm 6.1.7]. Many-one equivalence and degrees [Cut., Ch. 9.1 and 9.2]. Post's problem: [Cut., Problem 9.5.11]. Note that I mistakenly said in class that this problem had been open for a long time for many-one reducibility, while it actually was the case for more elaborate Turing reducibility based on the notion of an oracle [Cut., Ch. 9.4], also discussed by us. Simple sets [Cut., Ch. 7.4] (they actually provide an example of an intermediate r.e. degree in the many-one framework, see [Cut., Cor. 9.3.6]). Effective (recursive) operators and their simple properties: [Cut., Ch. 10.1]. Myhill-Shepherdson theorem [Cut., Ch. 10.2]. Kleene's fixed point theorem [Cut., Ch. 10.3]. First-order logic [Mend., Ch. 2; Cut., Ch. 8.1].
- Fifth week: Peano Arithmetic [Mend., Ch. 3.1]. 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. [4] is an excellent survey on decidable theories. Quantifier elimination technique and dense linear orders [Mend., page 110 (Ch. 2.12)]. 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 [5]. Asymptotic extremal combinatorics is undecidable [6]; for the context see [7].
- Sixth week (short): Kolmogorov Complexity: the basic text is [8], but most of the simple things we are doing in class are covered already in [9, Chapter 6.4]. Invariance Theorem [9, Thm. 6.27]. Incompressible strings [9, Def. 6.28, Thm. 6.29-6.32]. Conditional Kolmogorov complexity [8, Def. 2.1.1 and 2.1.2]. Algorithmic Prefix Complexity (just mentioned) [8, Ch. 3]. Classical information theory [8, Ch. 1.11].
- Seventh week: Classical information theory (cntd.) Conditional Kolmogorov complexity behaves as expected [8, Thm. 2.8.2]. Random infinite sequences [8, Ch. 2.5.2]. Prefixes of random sequences have large Kolmogorov complexity [8, Theorem 2.5.4]. Speed-up Theorem (without proof) [Cut., Thm. 12.2.1]. Gap Theorem (without proof) [Cut., Thm. 12.3.1]. Complexity classes, DTIME [9, Ch. 7.1; 10, Ch. 1.6]. Discussion [11; 9, Ch. 7.2; 10, Ch. 1.6]. Time Hierarchy Theorem [9, Thm. 9.10; 10, Thm. 3.1]. Space Hierarchy Theorem (without proof) [9, Thm. 9.3]. Relations between time and space [10, Thm. 4.2]. Class P [10, Ch. 1.6].
- Eighth week (long): Strong Church-Turing thesis [10, Ch. 1.6]. Karp reductions [10, Ch. 2.2]. Class NP [10, Ch. 2.1]. NTIME and the equivalence of two definitions [10, Ch. 2.1.1]. Universal NP-complete problem [10, Thm. 2.9]. Cook-Levin Theorem [9, Thm. 7.37]. 3-SAT is NP-complete [9, , Cor. 7.42]. Examples of NP-complete problems [12; 9, Ch. 7.5; 10, Ch. 2.4], see also Wikipedia link. Bounded version of Hilbert's tenth problem is NP-complete [13]. Solvability of quadratic equations in free groups [14]. TQBF and its PSPACE-completeness [10, Thm. 4.13]. Savitch's theorem [10, Ch. 4.2.1]. Other complete problems for PSPACE and EXPTIME with references can be found here and here (beware that the discussion in [10, Ch. 4.2.2] is somewhat incorrect, and most problems called there PSPACE-complete are actually EXPTIME-complete). Ladner's theorem (without proof) [10, Ch. 3.3]. Oracle machines [10, Ch. 3.4]. Limits of diagonalization [10, Thm. 3.7]. Polynomial-time hierarchy [10, Ch. 5].
- Tenth week:Randomized computations, definitions [10, Ch. 7.1 and 7.3]. BPP is strange [10, Ch. 7.5.3]. Error-reduction [10, Thm. 7.10]. $BPP\subseteq \Sigma_2^p$ (without proof) [10, Thm. 7.15]. Deterministic interactive proofs [10, Ch. 8.1.1]. Interactive proofs [10, Ch. 8.1]. Quantifier representation of AM [10, Figure 8.2]. Protocol for graph non-isomorphism [10, Ch. 8.1.3]. AM collapses for finitely many rounds (without proof) [15]. Public coin model is equivalent to the private one (without proof) [10, Thm 8.12]. IP=PSPACE (with a sketch of a proof) [10, Ch. 8.3]. MIP=NEXP (without proof) [10, Ch. 8.5; 16].

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. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
5. 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.
6. H. Hatami, S. Norin, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc., 24 (2011), 547-565.
7. A. Razborov, Flag Algebras, Journal of Symbolic Logic, Vol. 72, No 4, 2007, pages 1239-1282.
8. M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, third edition, Springer, 2008.
9. M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
10. S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.
11. S. Cook, Computational Complexity of Higher Type Functions, Proceedings of 1990 Intern. Congress of Mathematicians, Kyoto, Japan, Springer, 1991, 55-69.
12. M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
13. 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.
14. 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.
15. L. Babai, S. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, J. Comput. Syst. Sci., 36(2): 254-276, 1988.
16. L. Babai, L. Fortnow, L. Lund, Non-determinisitc exponential time has two-prover interactive proofs, Computational Complexity, 1:3-40, 1991.