CMSC 385001: Computability and Complexity Theory
Course description. See also the previous version of this course (some changes are anticipated).
Spring 2014: Tuesday, Thursday 1:30pm2: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 writeup of the solutions. If you work with other people, you must put their names clearly on the writeup.

Progress and references.

First week: Primitive recursive functions [Cutland, Chapters 2.12.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 DavenportSchinzel
sequences [3, Section 1.1]. Bounds on the length of DSsequences (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
firstorder 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 URMcomputable [Cut., Theorem 3.2.2]. Markov Normal Algorithms [Mend., Ch. 5.5; Cut., Ch. 3.5]. For a lovely
discussion of KolmogorovUspensky machines see [4]. ChurchTuring 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]. Manyone reducibility [Cut., Ch. 9.1]. smn 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]. MyhillShepherdson 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.) Firstorder 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 firstorder 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 secondorder systems sometimes are useful. Robinson's Arithmetic, called RR in [Mend., Ch. 3.4]. Deduction Theorem [Mend., Ch. 2.4, Prop. 2.5]. Pure firstorder 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.296.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]. Machineindependent complexity, Blum's axioms [Cut., Ch. 12.1]. Speedup 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 worstcase 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 ChurchTuring 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 NPcomplete problem [11, Thm. 2.9]. CookLevin Theorem [10, Thm. 7.37]. 3SAT is NPcomplete [10, , Cor. 7.42].
Examples of NPcomplete problems [14; 10, Ch. 7.5; 11, Ch. 2.4], see also Wikipedia
link. Bounded version of Hilbert's tenth problem is NPcomplete [14]. Solvability of quadratic equations in free groups is NPcomplete [15].

Ninth week: Examples of NPcomplete problems (cntd). TQBF and its PSPACEcompleteness
[11, Thm. 4.13]. Savitch's theorem [11, Ch. 4.2.1]. ImmermanSzelepcsenyi 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:
BakerGillSolovay Theorem [11, Thm. 3.7]. Polynomialtime hierarchy [11, Ch. 5]. Randomized computations, definitions [11, Ch. 7.1 and 7.3]. BPP is strange [11, Ch. 7.5.3]. SipserGacs Theorem [11, Thm. 7.15].

Tenth week (short): SipserGacs Theorem (cntd). Errorreduction [11, Thm. 7.10]. Interactive proofs: an overview; for missing details see [11, Ch. 8].

Literature.

N. J. Cutland, Computability, Cambridge University Press, 1980.

E. Mendelson, Introduction to Mathematical Logic, fifth edition, CRC Press, 2009.

M. Sharir and P.K. Agarwal, DavenportSchinzel Sequences and Their Geometric Applications,
Cambridge University Press, 1995.

Y. Gurevich, On Kolmogorov Machines And Related Issues,
Bulletin of European Assoc. for Theor. Comp. Science, 35, 1988, pages 7182.

M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.

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, 197217.

H. Hatami, S. Norin, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc., 24 (2011), 547565.

A. Razborov, What is a Flag Algebra?, Notices of the AMS, 60(10): 13241327, 2013.

M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, third edition, Springer, 2008.

M. Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.

S. Arora, B. Barak, Computational Complexity: a modern approach, Cambridge University Press, 2009.

A. Razborov, Foundations of computational complexity theory, Surveys in Modern Mathematics, London
Mathematical Society Lecture Note Series, No. 321, 2005, pages 186202.

S. Cook, Computational Complexity of Higher Type
Functions, Proceedings of 1990 Intern. Congress of Mathematicians,
Kyoto, Japan, Springer, 1991, 5569.

M. R. Garey, D, S, Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness,
W. H. Freeman, 1979.

K. Manders, L. Adleman, NPcomplete decision problems for quadratic polynomials, Proceedings of the
Eighth Annual ACM Symposium on Theory of Computing, pages 2329, 1976.

O. Kharlampovich, I.G. Lysenok, A.G. Myasnikov, N.W.M. Touikan, The Solvability Problem for Quadratic
Equations over Free Groups is NPComplete , Theory of Computing Systems, vol. 47, No 1, pages 250258, 2010.