Computational complexity

Winter 2019 at ENS Lyon

General information

This course will cover the basics of computational complexity theory. We will try to cover the following topics.



The grading scheme will take into account The general policy is that 1/2 of the grade is determined by the final exam.


Date Topic References
Jan 30th The class P and the class NP. Nondeterministic Turing machines, equivalent definition of NP.
NP-hardness. Example NP-complete problem. Statement of NP-completeness of SAT
Lecture notes (from 2014 offering)
Chap 1 of [AB], Sec 2.1, 2.2 and beginning of 2.3 of [AB]
Feb 6th Proof that SAT is NP-hard. (Check these notes for a proof of NP-completeness of SAT for a RAM model.)
Class coNP. NP and coNP are in EXP. Deterministic time hierarchy theorem.
Chap 2 et 3.1 of [AB]
Feb 13th Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete. Chap 4.1 and 4.2 of [AB]
Feb 27th Space hierarchy theorem. Composition theorem for space. NSPACE(S) in SPACE(S^2) (Savitch theorem).
Class NL, NL-hardness PATH is NL-complete. State NL = coNL.
Sec 4.2 and 4.3 (space complexity) of [AB]
Mar 6th Oracle Turing machines. Existence of oracles A,B with P^A=NP^A and P^B \neq NP^B. Polynomial hierarchy. If \Sigma_i = \Pi_i then the hierarchy collapses. Chap 3 and 5 in [AB]
Mar 13th Midterm exam. Definition of polynomial hierarchy with oracles. Start boolean circuits. Chap 5 of [AB]
Mar 20th Boolean circuits, P included in P/poly, uniformity condition for circuit family
TMs with advice, Karp-Lipton theorem: If NP included in P/poly, then the polynomial hierarchy collapses.
Chap 6 of [AB]
Mar 27th Randomized computation: BPP, relation to P/poly and polynomial hierarchy. Chap 7 of [AB]
Apr 3rd Communication complexity. Lower bound using fooling set bound, equality and disjointness. Chap 13 of [AB]
Apr 10rd Communication complexity. Application to streaming lower bounds. Randomized communication complexity. Discrepency method and application to the inner product function. Chap 13 of [AB]