Computational Complexity (May-Aug 2012)

Instructor:                    Debrup Chakraborty  (debrup(AT)

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

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

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


Home works : Home work 1 (due June 26) 
Home work 2 (due July 24) Home work 3 (Due Aug 17)



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 (to be filled up as we proceed)

8th May    Introduction

10th May    No class: Mothers day

15th May    Models of Computation: 
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.
    Arora- Barak 1.1-1-3

17th May    Turing Machines: Encoding Turing Machines with strings. Universal Turing Machines. A theorem about the slow down of a Universal Turing machine when simulating another machine.
                    Diagonalization: Some facts about infinite sets. Cantors proof of the fact that real numbers are not countable. Discussion on hierarchies of infinity and the continuum hypothesis
                    Computability: Discussions on the fact that there exists functions which are not computable. The function UC and the proof that it is not computable.
                    Arora-Barak 1.4, 1.5.
Additional readings: A note about infinite sets. Some more links about infinite sets.

22May        Computability: There exist more functions from strings to strings than Turing machines. The halting problem.
                   Some historical facts involving computability theory: Hilbert's 2nd, 10th and the Entscheidungsproblem, Godel's incompleteness theorems, Results of Turing and Church. The Church-Turing
Arora-Barak 1.5. Additional readings/viewings: Hilbert's Problems, Entscheidungsproblem, Godel's incompleteness theorems, The documentary "Dangerous Knowledge"

24May        Basic Complexity Classes: DTIME, NTIME, P, NP, coNP, EXP, NEXP

29th May    Reductions and NP completeness: Polynomial time reductions. Karp reductions and Cook reductions. NP completeness. Search problems, NP relations and self reducibility.
Arora-Barak 2.2, 2.5. Goldreich's notes

4th Jun        Cooks Theorem: CNF formulas, CNF formulas can represent any Boolean function, Oblivious Turing machines, proof of Cooks theorem.
Arora-Barak 2.3.

6th Jun        More reductions: 3SAT, CLIQUE, INDEPENDENT SET, VERTEX COVER are NP complete. coNP completeness, TAUTOLOGY is coNP complete.
Arora-Barak 2.4, 2.6

12th Jun      Diagonalization: Deterministic and non-deterministic time hierarchy theorems, Ladner's theorem.
Arora-Barak 3.1, 3.2, 3.3    Additional readings from Lipton's Blog: On NP intermediate problems, On Diagonalization     

14th Jun      Diagonalization and Relativization:
Oracle Turing machines, Baker-Gill-Solovay Theorem, discussion on relativization and why the BGS theorem is considered as a barrier
                      in settling the P vs NP question. Informal discussions about other attempts and known barriers for solving the P vs NP question.
Arora-Barak 3.4.   Additional readings: Lipton's opinion on oracle results, a contrary opinion of Lance Fortnow, about the status of the P vs NP question by Fortnow

19th Jun       A quick revision of what has been done till date.
                     Introduction to Space complexity:

                      Arora-Barak  4.1. Additional readings: The post mentioned by Thomaz in class

21st Jun        Configuration graphs of Turing Machines: Configuration graphs of space bounded machine, size of a configuration of a space s(n) machine, SPACE(s(n))= DTIME 
                      (2^{O(s(n)), Savitch's theorem
                       Arora-Barak 4.1, 4.2.1

26th Jun      PSPACE completeness: PSPACE complete problems, quantified Boolean formulas, TQBF is PSPACE complete, winning strategies in games, the formula game.
                     Arora-Barak 4.2

28th Jun      No Class (Turing Symposium)

5th July      L and NL : Implicit log space computable functions, log-space reductions, NL completeness, PATH is NL complete. Certificate based definition of NL, Statement of Immerman
                   Szelepecsenyi Thm: NSPACE(s(n)) = coNSPACE(s(n))

                    Arora-Barak 4.3  

6th July      Polynomial Hierarchy: The classes , PH; Properties of polynomial hierarchy; complete problems in all levels of PH.
                    Arora-Barak 5.1, 5.2

10th July    Polynomial Hierarchy: Oracle based definitions.
                    Arora-Barak 5.5

12th July    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.
                    Arora-Barak 6

16th July    Revision
17th July    Test1
24th July    Boolean Circuits: Classes NC and AC.
                    Arora-Barak 6

26th July    Probalbilistic Computations: Randomized Turing machines. The classes RP, BPP and ZPP. Error boosting in RP and BPP. ZPP and algorithms with expected
                   poly time.
Arora-Barak 7

31st July    Probabilistic Computations: BPP in P/poly. BPP in \sigma_2^p. Randomized reductions.
                    Arora-Barak 7

2nd Aug    Interactive proofs: Proof as an interaction. Alternative view of NP. The classes IP and AM. Interactive proof for Graph non Isomorphism.
                    Arora-Barak 8             Additional readings: A brief history of the PCP theorem          (this document traces the history of development of interactive proofs)