Computational complexity

Winter 2018 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.)
Chap 2 et 3.1 of [AB]
Feb 13th Space complexity. L, NL, PSPACE. Relation to time classes. Chap 4.1 and 4.2 of [AB]
Feb 27th Space hierarchy theorem. Composition theorem for space. Sec 4.2 and 4.3 (space complexity) of [AB]
Mar 6th Recall the classes we have seen.
TQBF is PSPACE complete. PSPACE = NPSPACE. NSPACE(S) in SPACE(S^2) (Savitch theorem). NL-hardness PATH is NL-complete.
Chap 4 and Sec 3.4 of [AB]
Mar 13th Midterm exam. State NL = coNL (proof in tutorial). Oracle Turing machines
Mar 20th Proof of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B.
Polynomial hierarchy with alternating quantifiers and with oracle machines. If \Sigma_i = \Pi_i then the hierarchy collapses.
Definition of polynomial hierarchy with oracles.
Sec 3.4, 5.1, 5.2, 5.5 of [AB]
Mar 27th 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. Definition of BPP.
Sec 6.1, 6.2, 6.3, 6.4 of [AB]
Apr 3rd Randomized computation: BPP \in P/poly, BPP in poly hierarchy.
Starting quantum computation, representation of quantum states.
Sec 7.1, 7.3, 7.4, 7.5 of [AB]
Watrous' lecture notes on introduction to quantum computing