Computational
Complexity (MayAug 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:0012:00
Grading: 4 Home works (60%), 2 Tests (40%)
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
nonuniform
models of computation; Randomization, randomized complexity classes, examples
of randomized algorithms;
Interactive proof systems; Probabilistic checking of proofs and the PCP
theorem.

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 ktape Turing machines, examples
on constructing Turing machines, discussions on why the alphabet size or
number of tapes does not matter. 
Sections 1.11.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. 
Section 1.4 of AB, some notes on infinite
sets 
more 
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. 
Section
1.5 of AB 
Wikipedia
articles on: An article about Turing. 
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 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, CookLevin
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.52.7 of AB 

7^{th} June 
No class 


9 
9^{th} June 
Diagonalization and Relativization: Deterministic and nondeterministic 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. 
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 polytime 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 (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 





