Les "figures jointes" du TD 9 proviennent du livre Computational complexity de Papadimitriou.
Sylvain Périfel - TD1 : oracles et la hiérarchie polynomiale
- TD2 : la classe DP, classes avec conseil
- TD3 : langages creux et langages unaires
- TD4 : diagonalisation, utilisation des théorèmes de hiérarchie
- TD5 : classes probabilistes 1 (RP principalement)
- TD6 : classes probabilistes 2 (BPP principalement)
- TD7 : classes probabilistes et de comptage (RP, BPP, PP, #P)
- TD8 : classes de comptage (PP, #P, parity-P)
- TD9 : classes de comptage, suite (#P, parity-P)
- TD10 : protocoles interactifs (IP, MIP)
- TD11 : protocoles interactifs (IP, AM)
- TD12 : PCP (probabilistically checkable proofs)
Partiel après le TD 7