Computational complexity

Winter 2017 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
Feb 15th 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]
Mar 1st 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]
Mar 8th Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete. Chap 4.1 and 4.2 of [AB]
Mar 15th Proof of PSPACE-completeness of TQBF. PSPACE = NPSPACE. NSPACE(S) in SPACE(S^2) (Savitch theorem).
Class NL, NL-hardness PATH is NL-complete. Stated NL = coNL.
Sec 4.2 and 4.3 (space complexity) of [AB]
Mar 22th Proof NL = coNL. Oracle Turing machines. Statement of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B Chap 4 and Sec 3.4 of [AB]
Mar 29th 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]