Ce cours prolonge "Complexité", nous aborderons plus en profondeur la théorie de la complexité algorithmique et les notions de difficulté et complétude pour une classe de complexité.
-
NP non-déterministe, équivalence avec la caractérisation existentielle (vérificateur déterministe de certificats).
-
Réductions many-one polynomiales, NP-complétude, théorème de Cook-Levin.
-
Problèmes complets pour coNP, les niveaux de la hiérarchie polynomiale, PSPACE, EXP.
- Problèmes fortements NP-complets.
-
Théorèmes de Ladner (P-intermédiaires), Mahaney (langages creux), Savitch (NPSPACE), Toda (PH dans P^#P).
Bibliographie : S. Perifel, Complexité algorithmique, Ellipses, 2014 (https://www.irif.fr/~sperifel/complexite.pdf).
