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.

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.