Responsable : Jean Goubault-Larrecq (LSV, ENS Cachan).

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-B-10 at ENS Paris-Saclay (Bât. Sud-Ouest), each Thursday, from 08h30 to 10h30, followed by exercise sessions from 10h45 to 12h45.

Planning: début du cours le 19 sept 2024. Début de la 2ème partie du cours: 14 nov 2024.

Evaluation: Two written exams (see exams from previous years at bottom of page).

Partial exam : Nov. 7th, 2024 from 10h30 to 12h30.

Final exam: Thursday, Jan. 16th 2025, same room (1B10), 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.

La théorie de la complexité va bien au-delà de celle de la NP-complétude. Le but de ce cours est d'aller regarder un certain nombre d'autres constructions fondamentales de la théorie de la complexité: complexité en espace, notions de machines alternantes, ou randomisées. On y verra quelques théorèmes fascinants: l'équivalence du temps alternant et de l'espace déterministe par exemple, ou le théorème IP=PSPACE de Shamir.

The course is based on the following lecture notes polycopié (1st part) and polycopié (2nd part).

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.

What we covered in class:

• Introduction. Deterministic and nondeterministic Turing machines
• Def (2.1) TIME(f), SPACE(f), NTIME(f), NSPACE(f), .. P, NP, L, NL, ..
• Compression Thm (2.2): SPACE(O(f(n))) ⊆ SPACE(f(n)) and NSPACE(O(f(n))) ⊆ NSPACE(f(n))
• Determinization: For proper function f, NTIME(f(n)) ⊆ SPACE(f(n)) and NSPACE(f(n)) ⊆ TIME(2^{(f(n)+log n)})

exercise sheet

What we covered in class:

• A k-worktape (N)TM in space f(n) running on input x visits at most ≈ |Q| × |𝛤|^f(n) x n × f(n)^k different configurations, i.e. O(n) x 2^O(f(n)), with n≝|x|
• (2.3) GAP, i.e. the “Graph Accessibility Problem” (for finite directed graphs), is in NL (aka NLOGSPACE i.e. NSPACE(log n))
• (2.6) GAP is in SPACE(log²(n))
• (2.4) NL ⊆ P (aka PTIME) and NL ⊆ SPACE(log²n)
• (2.9) Thm (Savitch 1970). NSPACE(f(n)) ⊆ SPACE(f²(n)) when f is proper & ≥log
• (2.10) Hence NPSPACE=NSPACE(n^O(1))=SPACE(n^O(1))=PSPACE

exercise sheet

What we covered in class:

• (2.12) Def. logspace reductions
• (2.11) Logspace reducibility, L ≤ L' is reflexive and transitive
• Def. 𝒞-complete problems for a class 𝒞
• (2.13) Thm. GAP is NL-complete
• Def. co𝒞 and coL for 𝒞 a class of problems (or languages) and L a problem
• (2.16) coGAP is in NL, hence (2.17) coNL = NL (Immerman-Szelepcsényi 1987)

What we didn't have time to see but can be found in the lecture notes:

• L, NL, P, NP, …, are closed under reducibility
• (2.14) Thm (Cook 1971). SAT is NP-complete

Exercise sheet

What we covered in class:

• (3.1;3.2) Alternating Turing machines. The classes ATIME(f) & ASPACE(f) are closed under complementation
• QBF (Quantifid Boolean Formulae) is in PSPACE and in APTIME
• (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete and APTIME-complete, hence PSPACE=APTIME.
• Circuits and their evaluation. MCV = CIRCUIT-VALUE[∧,∨] is in PTIME and in ALOGSPACE
• (3.18) MCV is PTIME-complete & ALOGSPACE-complete, entailing PTIME=ALOGSPACE, i.e. 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. AEXPTIME=EXPSPACE from AP = PSPACE and EXPTIME=APSPACE from P=AL.
• HORNSAT is PTIME-complete

Exercise sheet

What we covered in class:

• TM machines that access an oracle O (can be any language ⊆A^*). In a run of M^O, there is a special query tape where the TM might write a query q. When M enters the querying state, q is erased and the TM jumps to state s_yes or s_no depending on whether q∊O. When measuring space usage, the query tape in counted.
• Def: (given a language O) ℳ^O for a class ℳ of machines, e.g. P^O, NP^O, etc., similarly P^𝒞, NP^𝒞, etc. for a class 𝒞 of oracles.
• Some problems in P^SAT: UNSAT, SAT-UNSAT, UNIQ-SAT (Boolean formulae with only one satisying valuation), PARITY-SAT ≝ {(𝜑1,…,𝜑n) such that the number of satisfiable 𝜑i's is odd}, MAX-SAT ≝ {satisfiable Boolean formulae 𝜑(x1,..,xn) such that the lexicography largest satisfying valuation v_min (exists and) has v_min(xn)=true}, etc.
• Def (the polynomial hierarchy): PH ≝ all levels Σ_k with Σ₀≝Δ₀=Θ₀=P(=PTIME) and Σ_k+1≝NP^Σ_k, Δ_k+1≝P^Σ_k, Θ_k+1≝P^{Σ_k[O log n]}, and Π_k≝co(Σ_k).
• Facts: Δ₁=Θ₁=P and Σ₁=NP. Also Π_k=(coNP)^Σ_k where coNP seen as a class of machines comprises all polynomial-time TMs with only universal states.
• Thm: (Σ_k-1 ∪ Π_k-1) ⊆ Θ_k ⊆ Δ_k ⊆ (Σ_k ∩ Π_k).
• Thm: Σ_k ⊆ PSPACE^PSPACE = PSPACE for all k, hence PH ⊆ PSPACE.
• Thm: If PH=PSPACE then PH has a complete problem. If PH has a complete problem then PH coincides with some Σ_n level (we say “PH collapses”).
• Some complete problems for specific levels in PH: the ∃^*∀^* fragment of QBF is Σ₂-complete, in fact the ∃^*∀^*∃^*∀^*.. (∃^*/∀^*)_k fragment is Σ_k-complete; PARITY-SAT is Θ₂-complete; MIN-SAT and UNIQ-TSP (graphs with a unique Hamiltonian circuit of minimal length) are Δ₂-complete.
• Thm: Θ_k+1 = P_‖^Σ_k, 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): BH ≝ all levels BH_k with BH₁≝NP, BH_2k≝BH_2k-1⋀coNP, and BH_2k+1≝BH_2k⋁NP. DP is another name for BH₂, i.e. NP⋀coNP. Recall that 𝒞⋀𝒞' is defined as {L∩L'|L∊𝒞 and L'∊𝒞'}, so that one has 𝒞∩𝒞' ⊆ 𝒞,𝒞' ⊆ 𝒞⋀𝒞' (NB: the last inclusion assumes that 𝒞 and 𝒞' contain the universal languages A^* for any alphabet). There is a similar definition for 𝒞⋁𝒞.
• SAT-UNSAT and UNIQ-SAT are DP-complete, where DP=NP⋀coNP. There exist complete problems for each level of BH. If BH itself has a complete problem, then it collapses to some level BH_k.
• Facts: BH = P^NP[O(1)] hence BH ⊆ Θ₂. If BH=Θ₂ then BH collapses.

What we covered in class:

• Two counting problems #Cycle (≝ count the number of simple cycles in a given graph) and #SAT (≝ count the number of valuations satisfying a given boolean formula).
• #SAT is “difficult”, indeed if #SAT ∊ FP then P=NP. Perhaps #Cycle is easier, perhaps in FP (≝ the functions computable in polynomial-time).
• Fact: if #Cycle ∊ FP then in that case too P=NP. Proof is by reduction from HamiltonianGraph.
• Def. f ∊ #P iff f(x) is the number of accepting paths of a polytime NDTM on x. We can assume that all configurations of the TM have exactly 2 following configurations (or 0) and that all runs have length exactly p(n). Thus #P contains all the functions that counts the “solutions” to NP problems. E.g. #SAT and #Cycle belong to #P.
• Obviously if #P = FP then NP = P. We don't know whether the reverse implication holds. However if PSPACE = P then #P = FP.
• NB. #P is a class of functions but there are classes of decision problems based on counting accepting runs: PP, ⊕P.
• Def. f is #P-complete iff f in #P and g ≤ f for all g in #P. What reductions do we consider here? The strongest notion (parsimonious reduction) defines «g ≤ f iff g(x)=f(r(x)) for some easily computable r», e.g., r in logspace. We can relax and say, e.g., «g ≤ f iff g(x)=r'(f(r(x))) for some logspace r,r'». Or we can be more generous and define «g ≤ f iff g in FP^f».
• Thm. #SAT is #P-complete (under quasi-parsimonious reductions).
• 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 we showed #SAT ≤ #3SAT ≤ ℤ-PERMANENT ≤ {0,1}-PERMANENT so PERMANENT is #P-complete [Valiant 1979]. See wikipedia for a proof.

Exercise sheet

The slides of the second part of the course:

• Randomized Turing machines, RP, coRP, ZPP: covers Sections 1.1 and 1.2 of the polycopié (2nd part); the shorter version, and the video (November 4th, 2020);
• BPP (part 1): covers Section 1.3 and the Sipser-Gács-Lautemann theorem (Proposition 1.24) of the polycopié (2nd part); the shorter version, and the video;
• BPP (part 2): covers Section 1.4 (except for the Sipser-Gács-Lautemann theorem) of the polycopié (2nd part); the shorter version, and the video;
• Arthur vs. Merlin games (part 1): covers Section 3 up to and including Section 3.1 of the polycopié (2nd part); the shorter version, and the video;
• Arthur vs. Merlin games (part 2): covers Section 3.2 of the polycopié (2nd part); the shorter version, and the video;
• Sipser's coding lemmas, and consequences: covers Section 3.3 and Section 3.4 of the polycopié (2nd part); the shorter version; the video, covering this, plus the beginning of the next series (including ABPP⊆IP⊆PSPACE);
• Shamir's theorem: covers Section 3.5 of the polycopié (2nd part); the shorter version; and the video, covering the hard direction PSPACE⊆ABPP.
• NP=PCP and hardness of approximation: covers a good deal of Section 2 of the polycopié (2nd part); the shorter version.

The exercise sheets for the second part of the course:

• RP, coRP, ZPP
• BPP part 1
• BPP part 2
• TD 10
• TD 11
• TD 12
• TD 13

The class will be taught in English. Le polycopié est en français et les élèves peuvent poser des questions, intervenir, etc. en français.

Les questions des sujets d'examen seront en anglais. Les étudiants seront autorisés à rédiger leur copie d'examen en français ou en anglais.

Students are expected to be familiar with the concepts and formal definitions for Turing Machines, the class P (problems decidable in deterministic polynomial time), the class NP (non-deterministic polynomial-time), Cook's Theorem (SAT is NP-complete). These notions will only be very quickly recalled during the first classes.

Complexité et Calculabilité, Cryptologie.

Livres:

• Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• Sanjeev Arora and Boaz Barak. Computational Complexity. Cambridge University Press, 2009.
  (une pré-version est gracieusement disponible ici http://www.cs.princeton.edu/theory/complexity/)

• Sylvain Périfel. Complexité algorithmique. Ellipses, 2014. Disponible en ligne.

L'examen final 2022-23, en temps limité. Voici un corrigé.

Le partiel 2023-24, en temps limité. Voici un corrigé.

Le partiel 2024-25, en temps limité. Voici un corrigé.

L'examen final 2024-25, en temps limité. Voici un corrigé.