Computability and Computational Complexity: Spring 2015

Instructor C. Seshadhri
Office E2-347A
Email scomandu@
Where Porter Acad 249
When Tu Th, 12-1:45
Office hours Tu, 9-10, 2-3
Piazza









Books

• [DSW] "Computability, Complexity, and Languages", Davis, Sigal, Weyuker (Second edition)
• [S] "Introduction to the Theory of Computation", Sipser
• [HMU] "Introduction to Automata Theory, Languages, and Computation", Hopcroft, Motwani, Ullman (Third Edition)
• [M] "Introduction to Languages and The Theory of Computation", Martin (Online)

Lecture topics

• 3/31/15: Existence of uncomputable functions using diagonalization (Chapter 8.5 in [M])

• 4/2/15: Discussion of simple programming model, Introduction to Turing Machines, Starting to convert program to 2-dimensional Turing Machine (Chapter 7 in [M], Chapters 2, 6 in [DSW], Chapter 8-8.4 in [HMU])

• 4/7/15: Converted program to 2-dimensional Turing Machine, converting 2-dimensional and multi-headed Turing Machines to standard TMs (Same refs as previous class)

• 4/9/15: Definition of Primitive Recursion, showed that basic arithmetic, Boolean algebra, bounded quantification, and bounded minimalization are PR. Defined class of mu-recursive functions. (Chap 3 in [DSW], Chap 10-10.2 in [M]).

• 4/15/15: Simulating Turing Machines through Primitive Recusion with Minimalization. Completing the proof that C programming, Turing Machines and mu-recursive functions are computationall equivalent. Discussion of Church-Turing Thesis. (Chap 7.6 in [M], Chap 10.3-10.4 in [M])

• 4/16/15: Undecidability. Definitions of recursively enumerable, recursive/decidable. Proving undecidability of the halting problem. (Chap 9 in [M], Chap 9 in [HMU]) The proof in verse

• 4/21/15: Reductions. Proving that languages are undecidable through mapping reducibility. Focus on language of Turing Machines that accept no (or all) strings. (Chap 9-9.3 in [M], Chap 9-9.3 in [HMU])

• 4/23/15: More discussion on reductions, talking about it through code modifications. The discussion and proof of Rice's theorem. (Chap 9.3 in [M], Chap 9.3 in [HMU])

• 4/28/15: Proof of undecidability of Post's Correspondence Problem. Reduction from PCP to language on CFGs. (Chap 9.4 in [M], Chap 9.4 in [HMU])

• 4/30/15: The existence of quines (self-printing programs), Kleene's recursion theorem, and using it to prove undecidability (Chap 6.1 in [S]) Python quine based on proof, Self copier

• 5/5/15: Undecidability of number theory, proof of Goedel's incompleteness, using computability theory, and construction of unprovable sentence from recursion theorem (Chap 6.4 in [S])

• 5/7/15: Midterm

• 5/12/15: Introduction to computational complexity, definitions of classes based on runtime, a discussion of P and NP(Chap 11 in [M])

• 5/14/15: Polynomial-time reductions, NP-completeness, explanation of Cook-Levin theorem (Chap 11 in [M])

• 5/19/15: Proof of Cook-Levin theorem, normal forms of Boolean formulas, reducing SAT to CNF-SAT (Chap 11 in [M])

• 5/21/15: Completing reduction from SAT to CNF-SAT, reduction from SAT to 3SAT, 2SAT is in P, and CLIQUE is NP-complete (Chap 11 in [M])

• 5/21/15: Completing reduction from SAT to CNF-SAT, reduction from SAT to 3SAT, 2SAT is in P, and CLIQUE is NP-complete (Chap 11 in [M])

• 5/26/15: Hamiltonian Path is NP-complete, from CLIQUE to INDEPENDENT-SET to VERTEX-COVER (Chap 11 in [M], Chap 10 in [HMU], Chap 7 in [S])

• 5/21/15: 3-Colorability is NP-complete, discussion of coping with NP-hardness (Chap 7 in [S])