Complexité avancée (48h, 7 ECTS)

Responsable : Jean Goubault-Larrecq (LMF, ENS Paris-Saclay).

Plan et intervenants du cours 2026-2027

Lecturers: Philippe Schnoebelen then Jean Goubault-Larrecq for the course, and Guillaume Scerri for the exercise sessions (TD).

The lectures take place in room 1-O-07 at ENS Paris-Saclay, each Thursday, from 08h30 to 10h30, followed by exercise sessions from 10h45 to 12h45.

Planning: Course starts on Thu 17 Sep. 2026. Second period starts on Thu 12 Nov. 2026.
Evaluation: Two written exams (see exams from previous years at bottom of page).

Partial exam : Nov. 5th, 2026, room 1-O-07, 10h00 -12h00. No documents allowed. You can answer in French or in English.

Final exam: Thursday, Jan. 14th 2026, same room (1-O-07), ENS Paris-Saclay, 8h30-10h30. 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. 17, 2026: 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. 17, 2026

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))$}.

(2) Sep. 24, 2026

  • A {$k$}-worktape (N)TM in space {$f(n)$} running on input {$x$} visits at most ≈ {$|Q| \times |𝛤|^{k\,f(n)} \times n \times f(n)^k$} different configurations, i.e. {$O(n) \times 2^{O(f(n))}$}, with {$n≝|x|$}.
  • 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.3) {$\mathsf{GAP}$}, i.e. the "Graph Accessibility Problem" (for finite directed graphs), is in {$\mathsf{NL}$} (short for {$\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(n)}^2)$} 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. They are closed under composition.
  • {$\mathsf{L}, \mathsf{NL}, \mathsf{P}, \mathsf{NP}, ...$}, are closed under reducibility.
  • Def. 𝒞-complete problems for a class 𝒞.
  • (2.13) Thm. {$\mathsf{GAP}$} is {$\mathsf{NL}$}-complete.

(3) Oct. 1, 2026

  • Def. {$\mathsf{co}$}𝒫 and {$\mathsf{co}$}𝒞 for 𝒫 a problem and 𝒞 a class of problems.
  • Classes based on deterministic machines are closed by {$\mathsf{co}$}, e.g., {$\mathsf{coPTIME}$}={$\mathsf{PTIME}$}.
  • (2.16) {$\mathsf{coGAP}$} is in {$\mathsf{NL}$}, hence (2.17) {$\mathsf{coNL} = \mathsf{NL}$} (Immerman-Szelepcsényi 1987) and {$\mathsf{coGAP}$} is {$\mathsf{NL}$}-complete.
  • (2.14) Thm (Cook 1971). {$\mathsf{SAT}$} is {$\mathsf{NP}$}-complete. {$\mathsf{VALIDITY}$} is {$\mathsf{coNP}$}-complete.

Archives: exams from previous years

Partial exam 2024-25.

Partial exam 2025-26.

Final exam 2024-25, and a possible solution.

Final exam 2025-26, and a possible solution.