Computational Complexity (May-Aug 2010)

Instructor:                    Debrup Chakraborty  (debrup(AT)

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


Schedule  (we shall fill it as we proceed)



Topics covered

Compulsory reading

Additional readings


10th May





12th 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



17th 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



on infinite sets


19th 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 2nd problem, 10th 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)


24th 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)


26th 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


31st May

NP Completeness:  Some NP complete problems.

Section 2.3, 2.4 of AB


2nd 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

7th June

No class



9th June

Diagonalization and Relativization: Deterministic and non-deterministic time hierarchy theorems, Ladner’s theorem

Sections 3.1, 3.3 of AB



14th June

Diagonalization and Relativization: Oracle Turing machines, limits of diagonalization (Baker, Gill, Solovay theorem)

Section 3.4 of AB


16th 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



21st June

Space Complexity: Configuration graphs for Turing machines; Savitch’s theorem and its implications; proving that TQBF is PSPACE complete

Chapter 4 of AB



23rd 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



28th June

PATH is NL complete, NL =coNL

Section 4.3 of AB


30th June

Review and some problem solving


5th July

Test 1



7th 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



14th 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




19th July

Boolean Circuits: Proof of Karp Lipton’s theorem, Shanon’s theorem on circuits, the classes AC and NC



21th July

Randomized Computation: Probabilistic Turing Machines, The complexity clases BPP, RP and ZPP, Error reduction in BPP and RP



26st July

Review on HW 2

Randomized Computation: Some randomized algorithms, equality of strings, polynomial identity testing




28th July

Randomized Computation: ZPP and expected poly-time algorithms, Adlemans Theorem (BPP contained in P/poly), Gacs Sipsers Theorem (BPP contained in )




2th 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



4th Aug

Interactive Proofs



9th Aug

No class (Latincrypt



11th Aug

No class (Latincrypt)



16th Aug



18th Aug

Test 2