-
First week: Primitive recursive functions [Cutland, Chapters 2.1-2.4; Mendelson, Chapter 3.3]. The Ackermann function [Cut., Ch.2, Example 5.5] is not primitive recursive.
Recursive functions [Cut., Ch. 3.2 and 2.5; Mend., Ch. 3.3]. Turing machines [Mend., Ch. 5.1; Cut., Ch. 3.4].
-
Second 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 $\leq_m$ and equivalence $\equiv_m$ [Cut., Ch. 9.1]. s-m-n Theorem [Cut., Ch. 4.4].
-
Third week: First-order logic [Mend., Ch. 2; Cut., Ch. 8.1]. 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. [Rabin] is an excellent survey on decidable theories.
-
Fourth week: 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 [AdianMakanin].
Degree of computability and Post problem [Cut., Ch. 9.5]. Kolmogorov Complexity: the basic text is [Li Vitanyi], but most of the things we did in class
are covered already in [Sipser, Chapter 6.4]. Invariance Theorem [Sip., Thm. 6.27]. Incompressible strings [Sip., Def. 6.28, Thm. 6.29-6.32]. Classical information theory
[LiVit., Ch. 1.11]. Symmetry of algorithmic information [LiVit., Thm. 2.8.2].
-
Fifth week: Machine-independent complexity [Cut., Ch. 12.1]. Speed-up Theorem, simplified version [Cut., Thm. 12.2.1].
Gap Theorem (without proof) [Cut., Thm. 12.3.1]. Complexity classes, DTIME [Sip., Ch. 7.1; AroraBarak, Ch. 1.6]. Discussion
[Cook; Sip., Ch. 7.2; ArBar., Ch. 1.6]. Time Hierarchy Theorem [Sip., Thm. 9.10; ArBar., Thm. 3.1].
From now on, all references are to the book by Arora and Barak, unless stated otherwise.
-
Sixth week: Space Hierarchy Theorem [Sip., Thm. 9.3]. Relations between time and space [Thm. 4.2]. Class P and strong
Church-Turing thesis [Ch. 1.6]. Karp reductions [Ch. 2.2]. Class NP [Ch. 2.1]. NTIME and the equivalence of two
definitions [Ch. 2.1.1]. Universal NP-complete problem [Thm. 2.9]. Cook-Levin Theorem [Sip., Thm. 7.37]. 3-SAT is
NP-complete [Sip., Cor. 7.42].
-
Seventh week: Examples of NP-complete problems [GaJo; Sip., Ch. 7.5; ArBar., Ch. 2.4], see also Wikipedia
link. Bounded version of Hilbert's tenth problem is NP-complete [MaAd]. Solvability of quadratic equations in free groups [Kha et al.]. TQBF and its PSPACE-completeness
[Thm. 4.13]. Savitch's theorem [Ch. 4.2.1]. Other complete problems for PSPACE and EXPTIME with references can be found
here
and here (beware that the discussion in [ArBar, Ch. 4.2.2] is somewhat incorrect, and most problems called
there PSPACE-complete are actually EXPTIME-complete). Ladner's theorem [Ch. 3.3]. Oracle machines [Ch. 3.4]. Limits of diagonalization [Thm. 3.7].
-
Eighth week: Polynomial-time hierarchy [Ch. 5]. Randomized computations, definitions [Ch. 7.1 and 7.3]. BPP is strange [Ch. 7.5.3]. Error-reduction [Thm. 7.10].
$BPP\subseteq \Sigma_2^p$ [Thm. 7.15]. Deterministic interactive proofs [Ch. 8.1.1].
-
Nineth week: Interactive proofs [Ch. 8.1]. Quantifier representation of AM [Figure 8.2]. AM collapses for finitely many rounds [BaMo].
Protocol for graph non-isomorphism [Ch. 8.1.3]. Public coin model is equivalent to the private one [Thm 8.12].
IP=PSPACE [Ch. 8.3].
-
Tenth week (short): IP=PSPACE (cntd). MIP=NEXP, sketch [Ch. 8.5; BaFoLu].