Exposé Bourbaki 895 : Le théorème PCP et ses conséquences en théorie de l'optimisation
Exposé Bourbaki 895 : The PCP Theorem
Astérisque | Exposés Bourbaki | 2003

- Année : 2003
- Tome : 290
- Format : Électronique
- Langue de l'ouvrage :
Anglais - Class. Math. : 68W25
- Pages : 19-36
- DOI : 10.24033/ast.602
Ces dix dernières années ont vu l'émergence d'un nouveau formalisme pour exprimer la e NP, basé sur la notion de vérification aléatoire de preuves. Ces travaux ont abouti à des résultats tout à fait surprenants, notamment sur la vérification de preuve en temps constant et l'inapproximabilité de certains problèmes d'optimisation NP-complets. Cet exposé fera un compte rendu de ces développements et esquissera les grandes idées du résultat principal de cette théorie : le théorème PCP. Aucune connaissance en informatique théorique ne sera requise.
Théorie de la complexité, algorithmes d'approximation, vérification de preuves