• Login

en fr

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, room 1N82, 10h00 -12h00. No documents allowed. You can answer in French or in English. Here is a tentative set of answers: bonus points if you report bugs/typos/...

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

TD1

(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.

TD2

(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.

TD3

(4) Oct. 9, 2025

• (3.1;3.2) Alternating Turing machines. The classes {$\mathsf{ATIME(f)}$} & {$\mathsf{ASPACE(g)}$} are closed under complementation
• {$\mathsf{QBF}$} (Quantifid Boolean Formulae) is in {$\mathsf{PSPACE}$} and in {$\mathsf{APTIME}$}
• (2.21) Thm (Stockmeyer-Meyer 1973) {$\mathsf{QBF}$} is {$\mathsf{PSPACE}$}-complete and {$\mathsf{APTIME}$}-complete, hence {$\mathsf{PSPACE=APTIME}$}.
• Circuits and their evaluation. {$\mathsf{CIRCUITVALUE}$} is in {$\mathsf{PTIME}$} and in {$\mathsf{ALOGSPACE}$}.
• (3.18) {$\mathsf{CIRCUITVALUE}$} is {$\mathsf{PTIME}$}-complete & {$\mathsf{ALOGSPACE}$}-complete, entailing {$\mathsf{PTIME=ALOGSPACE}$}, i.e. {$\mathsf{P=AL}$}.

What we did not have time to see but can be found in the lecture notes:

• (3.8) Padding lemma.
• (3.9 & 3.19) This yields e.g. {$\mathsf{AEXPTIME=EXPSPACE}$} from {$\mathsf{AP = PSPACE}$} and {$\mathsf{EXPTIME=APSPACE}$} from {$\mathsf{P=AL}$}.
• {$\mathsf{HORNSAT}$} is {$\mathsf{PTIME}$}-complete.

TD4

(5) Oct. 16, 2025

• Def: TM machines that access an oracle {$O$} (can be any language {$\subseteq A^*$}). In a run of {$M^O$}, there is a special query tape where the TM might write a query {$w$}. When {$M$} enters the querying state, {$w$} is erased and the TM jumps to state {$s_{\text{yes}}$} or {$s_{\text{no}}$} depending on whether {$w\in O$}. When measuring space usage, the query tape is counted.
• Def: (given a language {$O$}) {$\mathcal{M}^O$} for a class {$\mathcal{M}$} of machines, e.g. {$\mathsf{P}^O$}, {$\mathsf{NP}^O$}, etc., similarly {$\mathsf{P}^\mathcal{C}$}, {$\mathsf{NP}^\mathcal{C}$}, etc. for a class {$\mathcal{C}$} of oracles.
• Some problems in {$\mathsf{P}^\mathsf{SAT}$}: {$\mathsf{UNSAT}$}, {$\mathsf{SAT}$}-{$\mathsf{UNSAT}$}, {$\mathsf{UNIQ}$}-{$\mathsf{SAT}$} (Boolean formulae with only one satisying valuation), {$\mathsf{PARITY}$}-{$\mathsf{SAT} ≝ \{(\phi_1,...,\phi_n)$} s.t. the first satisfiable {$\phi_i$} had odd index {$i\}$}, {$\mathsf{MIN}$}-{$\mathsf{SAT} ≝ \{$}satisfiable Boolean formulae {$\phi(x_1,..,x_n)$} s.t. the lexicography first satisfying valuation {$v_\text{min}$} (exists and) has {$v_\text{min}(x_n)=\top\}$}, etc.
• Def: (the polynomial hierarchy): {$\mathsf{PH ≝}$} all levels {$\Sigma_k^p$} for {$k=0,1,2,3,..$} with {$\Sigma^p_0 ≝ \Delta_0^p ≝ \Theta_0^p ≝ \mathsf{P}$} {$(=\mathsf{PTIME})$} and {$\Sigma_{k+1}^p ≝ \mathsf{NP}^{\Sigma_k^p}$}, {$\Delta_{k+1}^p ≝ \mathsf{P}^{\Sigma_k^p}$}, {$\Theta_{k+1}^p ≝ \mathsf{P}^{\Sigma_k^p[O(\log n)]}$}, and {$\Pi_k^p ≝\mathsf{co}(\Sigma_k^p)$}.
• Facts: {$\Delta_1^p = \Theta_1^p = \mathsf{P}$} and {$\Sigma_1^p=\mathsf{NP}$}. Also {$\Pi_{k+1}^p =(\mathsf{coNP})^{\Sigma_k^p}$} where {$\mathsf{coNP}$} is here seen as the class of polynomial-time Turing machines that have only universal nondeterministic states.
• Thm: {$(\Sigma_{k-1}^p\cup\Pi_{k-1}^p) \subseteq\Theta_k^p\subseteq\Delta_k^p \subseteq (\Sigma_k^p\cap\Pi_k^p)$}.
• Thm: for any {$k$}, {$\Sigma_k^p \subseteq\mathsf{PSPACE}^{\mathsf{PSPACE}} =\mathsf{PSPACE}$}, hence {$\mathsf{PH}\subseteq\mathsf{PSPACE}$}.
• NB. If {$\mathsf{PH}=\mathsf{PSPACE}$} then {$\mathsf{PH}$} has a complete problem, e.g. {$\mathsf{QBF}$}. If {$\mathsf{PH}$} has a complete problem then {$\mathsf{PH}$} coincides with some {$\Sigma_k^p$} level (we say that "{$\mathsf{PH}$} collapses").
• Some complete problems for specific levels in {$\mathsf{PH}$}: the {$\exists^*\forall^*$}-fragment of {$\mathsf{QBF}$}, also called {$\Sigma_2$}-{$\mathsf{SAT}$}, is {$\Sigma_2^p$}-complete, in fact the {$\Sigma_k$}-{$\mathsf{SAT}$} fragment is {$\Sigma_k^p$}-complete. {$\mathsf{PARITY}$}-{$\mathsf{SAT}$} is {$\Theta_2^p$}-complete; {$\mathsf{MIN}$}-{$\mathsf{SAT}$} and {$\mathsf{UNIQ}$}-{$\mathsf{TSP}$} (graphs with a unique Hamiltonian circuit of minimal length) are {$\Delta_2^p$}-complete.
• Thm: {$\Theta_{k+1} = \mathsf{P}_‖^{\Sigma_k^p}$}, where polynomially many queries can be submitted to the oracle, but they have to be computed in advance so that they can all be answered "in parallel", in just one round.
• Def (the Boolean hierarchy): {$\mathsf{BH}$} ≝ all levels {$\mathsf{BH}_k$} with {$\mathsf{BH}_1 ≝ \mathsf{NP}$}, {$\mathsf{BH}_{2k} ≝ \mathsf{BH}_{2k-1} \bigwedge \mathsf{coNP}$}, and {$\mathsf{BH}_{2k+1} ≝ \mathsf{BH}_{2k} \bigvee \mathsf{NP}$}. {$\mathsf{DP}$} is another name for {$\mathsf{BH}_2$}, i.e., {$\mathsf{NP}\bigwedge\mathsf{coNP}$}. Recall that {$\mathcal{C}\bigwedge \mathcal{C}'$} is defined as {$\{L\cap L'~|~L\in\mathcal{C}$} and {$L'\in\mathcal{C}'\}$}, so that one has {$\mathcal{C}\cap\mathcal{C}' \subseteq \mathcal{C},\mathcal{C}' \subseteq \mathcal{C}\bigwedge\mathcal{C}'$} (NB: the last inclusion assumes that {$\mathcal{C}$} and {$\mathcal{C}'$} contain the universal languages {$A^*$} for any alphabet). There is a similar definition for {$\mathcal{C}\bigvee\mathcal{C}'$}.
• NB. {$\mathsf{SAT}$}-{$\mathsf{UNSAT}$} and {$\mathsf{UNIQ}$}-{$\mathsf{SAT}$} are {$\mathsf{DP}$}-complete, where {$\mathsf{DP}≝\mathsf{NP}\bigwedge\mathsf{coNP}$}. There exist complete problems for each level of {$\mathsf{BH}$}. But if {$\mathsf{BH}$} itself has a complete problem, then it collapses to some level {$\mathsf{BH}_k$}.
• Fact: {$\mathsf{BH} = \mathsf{P}^{\mathsf{NP}[O(1)]}$} hence {$\mathsf{BH}\subseteq\Theta_2^p$}. If {$\mathsf{BH}=\Theta_2^p$} then {$\mathsf{BH}$} collapses.
• Corresponding exercise sheet: TD5-2024.

(6) Oct. 23, 2025

• Two counting problems {$\mathsf{\#Cycle}$} (≝ count the number of covers by cycles in a given graph) and {$\mathsf{\#SAT}$} (≝ count the number of valuations satisfying a given boolean formula).
• {$\mathsf{\#SAT}$} is "difficult", indeed if {$\mathsf{\#SAT} \in \mathsf{FP}$} then {$\mathsf{P}=\mathsf{NP}$}. Perhaps {$\mathsf{\#Cycle}$} is easier, perhaps in {$\mathsf{FP}$} (≝ the functions computable in polynomial-time).
• Fact: if {$\mathsf{\#Cycle}\in\mathsf{FP}$} then in that case too {$\mathsf{P}=\mathsf{NP}$}. Proof is by reduction from {$\mathsf{HamiltonianGraph}$}.
• Def. {$f \in \mathsf{\#P}$} iff {$f(x)$} is the number of accepting paths of a polytime NDTM on {$x$}. Thus {$\mathsf{\#P}$} contains all the functions that counts the "solutions" to {$\mathsf{NP}$} problems. E.g. {$\mathsf{\#SAT}$} and {$\mathsf{\#Cycle}$} belong to {$\mathsf{\#P}$}.
• Obviously if {$\mathsf{\#P} = \mathsf{FP}$} then {$\mathsf{NP} = \mathsf{P}$}. We don't know whether the reverse implication holds. However if {$\mathsf{PSPACE} = \mathsf{P}$} then {$\mathsf{\#P} = \mathsf{FP}$}.
• NB. {$\mathsf{\#P}$} is a class of functions but there are classes of decision problems based on counting accepting runs, e.g., {$\mathsf{PP}$} or {$\mathsf{⊕P}$}.
• Def. {$f$} is {$\mathsf{\#P}$}-complete iff {$f$} in {$\mathsf{\#P}$} and {$g \leq f$} for all {$g$} in {$\mathsf{\#P}$}. What reductions do we consider here? The strongest notion, called parsimonious reductions, defines «{$g \leq f$} iff {$g(x)=f(r(x))$} for some easily computable {$r$}», e.g., {$r$} in logspace or in polytime. We can relax and say, e.g., «{$g \leq f$} iff {$g(x)=r'(f(r(x)))$} for some logspace or polytime {$r,r'$}», called many-one counting reductions, and usually implicitly assumed. Or we can be more generous and define «{$g \leq f$} iff {$g$} in {$\mathsf{FP}^f$}», called Turing counting reductions.
• Thm. {$\mathsf{\#SAT}$} is {$\mathsf{\#P}$}-complete.
• Computing the permanent of a matrix is related to counting the cycle-covers of a directed graph. The definition looks like computing the determinant. However [Valiant 1979] showed {$\mathsf{\#SAT}\leq\mathsf{\#3SAT} \leq \mathbb{Z}$}-{$\mathsf{PERMANENT}\leq \{0,1\}$}-{$\mathsf{PERMANENT}$} so {$\mathsf{PERMANENT}$} is {$\mathsf{\#P}$}-complete, evn when restricted to 0,1-matrices. See wikipedia for a proof.

TD6

Archives: exams from previous years

Final exam 2022-23.

Partial exam 2023-24.

Partial exam 2024-25.

Final exam 2024-25.