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.