D
ossier
29
« Bon, maintenant, on essaie le PCP ?»
l’algorithme PCP ? Non, l’aléa y est indispensable. Sans accès à des
bits
aléatoires, vous êtes condamné
à lire ma preuve dans sa totalité.
Ce qui est étonnant dans ce résultat, c’est que ma preuve au format PCP est forcément immune à un
nombre considérable d’erreurs : en effet, si vous ne piochez que 10 caractères au hasard, je peux me
permettre des milliers d’étapes erronées sans avoir crainte d’être pris en flagrant délit. Encore plus sur-
prenant, si ma preuve est entièrement correcte mais prouve autre chose, par exemple la conjecture de
Poincaré, vous vous en apercevrez tout de suite. Formellement, le théorème PCP s’exprime sous la forme
NP = PCP (log
n
, 1). Traduction : «
Toute solution d’un problème dans NP (une preuve) peut être écrite
en temps polynomial dans sa taille
n
de telle façon qu’elle puisse être vérifiée en consultant un nombre
constant de ses
bits
. Le nombre de
bits
aléatoires est au plus logarithmique en
n. »
Mathématiquement, l’algorithme PCP étend le concept de code correcteur d’erreurs aux fonctions : un
code traditionnel permet de maintenir l’intégrité syntaxique d’un signal en présence d’erreurs, tandis qu’un
code PCP maintient l’intégrité sémantique d’une preuve sujette à erreur. La vérification instantanée, quant
à elle, repose sur la notion de codes « localement décodables ». Ce résultat profond a des ramifica-
tions épistémologiques évidentes : une tradition philosophique remontant à Platon définit la connais-
sance comme une croyance vraie justifiée. La justification est nécessaire pour éviter la connaissance par
hasard. L’algorithme PCP nous apprend que l’aléa rend la vérification de la justification triviale. Au-delà
même des mathématiques et de l’informatique, cela semble être une contribution philosophique majeure !
