Computational Complexity (May-Aug 2010)

Instructor: Debrup Chakraborty (debrup(AT)cs.cinvestav.mx)

References: 1) Computational Complexity: A modern approach, Sanjeev Arora and Boaz Barak. (Text book, we shall refer as AB)
2) Computational Complexity: A conceptual perspective, Oded Goldreich

Classes: Monday and Wednesday from 10:00-12:00

Grading: 4 Home works (60%), 2 Tests (40%)

Home works Home work 1 (due June 21, 2010)
Home work 2 (due July 12, 2010)
Home work 3 (due August 16, 2010)

Topics (Tentative): Models of computation, Turing machines, Introduction to computability theory; Basic complexity
classes; NP completeness; Reductions; Examples of NP complete problems; Diagonalization and
Relativization, Ladner’s theorem, oracle Turing machines; Space complexity; Boolean circuits and
non-uniform models of computation; Randomization, randomized complexity classes, examples
of randomized algorithms; Interactive proof systems; Probabilistic checking of proofs and the PCP
theorem.

Schedule (we shall fill it as we proceed)

	Date	Topics covered	Compulsory reading	Additional readings
1	10^th May	Introduction
2	12^th May	Turing Machines: The need for a formal model of computation, introduction to Turing machines, the k-tape Turing machines, examples on constructing Turing machines, discussions on why the alphabet size or number of tapes does not matter.	Sections 1.1-1.3 of AB
3	17^th May	Turing Machines : The universal Turing machine, a theorem on the amount of slowdown in an universal Turing machine while simulating another TM. Some facts about infinite sets: Countable sets and non-countable sets, Cantor’s proof of the fact that the real numbers are not countable, discussion on the hierarchies of infinity and the continuum hypothesis.	Section 1.4 of AB, some notes on infinite sets	more on infinite sets
4	19^th May	Turing machines and Computability: Existence of functions which are not computable, proof of the fact there are more functions of the type f:{0,1}^n→{0,1} than the number of Turing machines, the halting problem and its significance. Some words about the history and philosophical implication of computability theory: Hilbert’s 2^nd problem, 10^th problem and the Entcheidungsproblem. Gödel’s incompleteness theorems, significance of the results of Turing and Church, the Church Turing thesis	Section 1.5 of AB	Wikipedia articles on: 1) Hilberts Problems 2) Entcheidungsproblem 3) Gödel’s theorems An article about Turing. An article on Post in Lipton’s blog. (this blog is very interesting, I recommend you to follow it)
5	24^th May	Basic Complexity Classes: DTIME, P: efficient computation and the class P; NTIME, NP: Nondeterministic Turing machines, two alternative views of the class NP; Polynomial time Karp reducibility, NP hard, NP Complete	Sections 1.6, 2.1, 2.2 of AB	Some interesting surveys worth reading: 1) The History and Status of the P vs. NP Question by Michael Sipser (contains a translation of Gödel’s letter that we mentioned in class) 2)P, NP and Mathematics - a computational complexity perspective by Avi Wigderson (a mathematical account intended for mathematicians) Conventional wisdom and P=NP (from Lipton’s blog)
6	26^th May	NP Completeness: Existence of NP complete problems, Boolean formulas, Conjunctive normal form, satisfiability, the language SAT, Cook-Levin Theorem	Section 2.3 of AB
7	31^st May	NP Completeness: Some NP complete problems.	Section 2.3, 2.4 of AB
8	2^nd June	Decision vs Search problems, the classes coNP, EXP and NEXP, some reflections about the P vs NP question	Sections 2.5-2.7 of AB
	7^th June	No class
9	9^th June	Diagonalization and Relativization: Deterministic and non-deterministic time hierarchy theorems, Ladner’s theorem	Sections 3.1, 3.3 of AB
10	14^th June	Diagonalization and Relativization: Oracle Turing machines, limits of diagonalization (Baker, Gill, Solovay theorem)	Section 3.4 of AB
11	16^th June	A quick revision of what has been done till the last class. Space Complexity: Introduction to space bounded computations, the classes SPACE, NSPACE, PSPACE, NPSPACE, L, NL with examples; PSPACE complete problems; Quantified Boolean formulas and the language TQBF	Chapter 4 of AB
12	21^st June	Space Complexity: Configuration graphs for Turing machines; Savitch’s theorem and its implications; proving that TQBF is PSPACE complete	Chapter 4 of AB
13	23^rd June	Space Complexity: Completing the proof of the fact that TQBF is PSPACE complete. Winning strategies for games, the formula game. Space hierarchy theorems; L, NL and NL complete problems.	Chapter 4 of AB
14	28^th June	PATH is NL complete, NL =coNL	Section 4.3 of AB
	30th June	Review and some problem solving
	5^th July	Test 1
15	7^th July.	Polynomial Hierarchy: The classes , PH; properties of polynomial hierarchy; complete problems in all levels of PH	Sections 5.1 and 5.2 of AB
16	14^th July	Polynomial Hierarchy: Alternating Turing machines and the oracle based definition Boolean circuits: Definitions, the class P/poly, Turing machines which take advice, P uniform and log space uniform circuits. Statements of Karp Lipton and Meyers theorems
17	19^th July	Boolean Circuits: Proof of Karp Lipton’s theorem, Shanon’s theorem on circuits, the classes AC and NC
18	21^th July	Randomized Computation: Probabilistic Turing Machines, The complexity clases BPP, RP and ZPP, Error reduction in BPP and RP
19	26^st July	Review on HW 2 Randomized Computation: Some randomized algorithms, equality of strings, polynomial identity testing
20	28^th July	Randomized Computation: ZPP and expected poly-time algorithms, Adlemans Theorem (BPP contained in P/poly), Gacs Sipsers Theorem (BPP contained in )
21	2^th Aug	Randomized Computation: Randomized reductions, the class BP.NP, Valiant Vazirani reduction Counting problems: Introduction to the class (sharp)P, (sharp)P complete problems, statement of Todas theorem
22	4^th Aug	Interactive Proofs
	9^th Aug	No class (Latincrypt
	11^th Aug	No class (Latincrypt)
	16^th Aug	Review
	18^th Aug	Test 2