Complexité avancée (48h, 7 ECTS)
Plan et intervenants du cours 2025-2026
The lectures take place in room 1-N-82 at ENS Paris-Saclay, each Thursday, from 08h30 to 10h30, followed by exercise sessions from 10h45 to 12h45.
Partial exam : Nov. 6th, 2025 from 10h30 to 12h30.
Final exam: Thursday, Jan. 15th 2025, same room (1N82), ENS Paris-Saclay, 8h30-11h30. All written documents allowed (I recommend printing selected excerpts from the lecture notes). No Internet access, no cell phone. You can answer in French or in English.
Motivations et objectifs du cours
Computational complexity goes well beyond the P vs. NP question. This class covers a few more fundamental notions: space complexity, alternating and randomized machines, etc. We will present some fascinating results like Shamir's IP=PSPACE theorem and walk through strange areas like the polynomial-time and the Boolean hierarchies.
Description du cours
The course is based on the following lecture notes polycopié (1st part) and polycopié (2nd part).
Starting Sep. 18, 2025: 1st part of the course
After each class, this section will be updated with a summary of the material actually covered.
Numbers, e.g. “(2.1)”, refer to statement in the lecture notes.
(1) Sep. 18, 2025
What we covered in class:
- Introduction. Deterministic and nondeterministic Turing machines.
- Def (2.1) {$\mathsf{TIME}(f), \mathsf{SPACE}(f), \mathsf{NTIME}(f), \mathsf{NSPACE}(f), .. \mathsf{P}, \mathsf{NP}, \mathsf{L}, \mathsf{NL}, ..$}.
- Compression Thm (2.2): {$\mathsf{SPACE}(O(f(n))) ⊆ \mathsf{SPACE}(f(n))$} and {$\mathsf{NSPACE}(O(f(n))) ⊆ \mathsf{NSPACE}(f(n))$}.
- Determinization: For proper function {$f$}, {$\mathsf{NTIME}(f(n)) ⊆ \mathsf{SPACE}(f(n))$} and {$\mathsf{NSPACE}(f(n)) ⊆ \mathsf{TIME}(2^{f(n)+\log n})$}.
(2) Sep. 25, 2025
- A {$k$}-worktape (N)TM in space {$f(n)$} running on input {$x$} visits at most ≈ {$|Q| \times |𝛤|^{f(n)} \times n \times f(n)^k$} different configurations, i.e. {$O(n) \times 2^{O(f(n)})$}, with {$n≝|x|$}.
- (2.3) {$\mathsf{GAP}$}, i.e. the "Graph Accessibility Problem" (for finite directed graphs), is in {$\mathsf{NL}$} (aka {$\mathsf{NLOGSPACE}$} i.e. {$\mathsf{NSPACE}(\log n)$}).
- (2.6) {$\mathsf{GAP}$} is in {$\mathsf{SPACE}(\log^2n)$}.
- (2.4) {$\mathsf{NL} ⊆ \mathsf{P}$} (aka {$\mathsf{PTIME}$}) and {$\mathsf{NL} ⊆ \mathsf{SPACE}(\log^2n)$}.
- (2.9) Thm (Savitch 1970). {$\mathsf{NSPACE}(f(n)) ⊆ \mathsf{SPACE}(f^2(n))$} when {$f$} is proper & {$≥\log$}.
- (2.10) Hence {$\mathsf{NPSPACE}=\mathsf{NSPACE}(n^{O(1)})=\mathsf{SPACE}(n^{O(1)})=\mathsf{PSPACE}$}.
- (2.12) Def. logspace reductions.
- Def. 𝒞-complete problems for a class 𝒞.
- (2.13) Thm. {$\mathsf{GAP}$} is {$\mathsf{NL}$}-complete.
(3) Oct. 2, 2025
- Def. {$\mathsf{co}$}𝒞 and {$\mathsf{coL}$} for 𝒞 a class of problems (or languages) and {$\mathsf{L}$} a problem.
- (2.11) Logspace reducibility, written {$\mathsf{L} ≤ \mathsf{L'}$}, is reflexive and transitive.
- (2.16) {$\mathsf{coGAP}$} is in {$\mathsf{NL}$}, hence (2.17) {$\mathsf{coNL} = \mathsf{NL}$} (Immerman-Szelepcsényi 1987).
What we didn't have time to see but can be found in the lecture notes:
- {$\mathsf{L}, \mathsf{NL}, \mathsf{P}, \mathsf{NP}, ...$}, are closed under reducibility.
- (2.14) Thm (Cook 1971). {$\mathsf{SAT}$} is {$\mathsf{NP}$}-complete. {$\mathsf{VALIDITY}$} is {$\mathsf{coNP}$}-complete.