Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorème PCP
Résumé
En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive. Plus précisément, NP est la classe des problèmes de décision qui ont des preuves pouvant être vérifiées de façon probabiliste en ayant accès à un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits aléatoires.
Le théorème PCP est très important en informatique théorique : il apporte notamment de nombreux résultats sur la difficulté d'approximer les problèmes algorithmiques.
Le théorème PCP affirme que, si l'on tolère une marge d'erreur, il est inutile de lire une démonstration en entier pour être convaincu de sa correction. On peut reformuler cette affirmation aussi comme suit : il existe une constante K telle que toute preuve mathématique P de longueur n peut être réécrite en une preuve P’ de longueur polynomiale en n, de sorte qu'il suffise d'examiner seulement K symboles de P’ (à l'aide d'un algorithme randomisé) pour être convaincu de l'exactitude de la preuve à 99 %.
vignette|Irit Dinur
vignette|Considérons une tranche de pain avec une goutte de confiture dessus. Il y a peu de chance de trouver la confiture en inspectant un échantillon du morceau de pain. Par contre, en étalant la confiture, on est quasiment sûr d'en trouver en inspectant un échantillon.
Lors de sa conférence plénière au congrès international des mathématiciens de 2010, Irit Dinur a utilisé une analogie pour faire comprendre ce théorème. Elle est rapportée en ces termes par Étienne Ghys :
Considérons le problème de vérifier une preuve pour un théorème mathématique. Puisque les preuves peuvent être longues et difficiles à vérifier dans leur intégralité, on peut chercher une façon de présenter une preuve de telle sorte qu'il suffise d'en vérifier une petite partie seulement pour juger la validité du théorème avec un niveau de confiance raisonnablement élevé.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.