Computational Complexity (May-Aug 2012)
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 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%)
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 (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
Thesis.
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: The classes SPACE,
NSPACE, PSPACE, NPSPACE, L, NL
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)