Tongs, bermuda et lunettes de soleil : d’entrée de jeu, on comprend qu’Avi Wigderson (Institute for Advanced Study de Princeton), lauréat du Prix Abel en 2021, est l’orateur le plus cool de cet ECM. Une impression que ne démentira pas son Abel Lecture, donnée dans un style décontracté et plein d’humour.

Dans The value of errors in proofs, Wigderson retraçait l’histoire de questions fondatrices sur une notion essentielle en mathématiques : la preuve. L’idée était de parler à la fois de preuve et de calcul, et de montrer l’intérêt de la méthodologie de la théorie de la complexité au service de la modélisation, de l’efficacité des algorithmes, de la classification…

Il commençait par rappeler le rêve de David Hilbert, formulé au début du XXe siècle : que vérité, prouvabilité et calculabilité soient équivalentes. Un rêve enterré dès les années 1930 par Kurt Gödel, avec son théorème d’incomplétude, démontrant l’existence de propositions indécidables (dont on ne peut prouver ni qu’elles sont vraies, ni qu’elles sont fausses), et Alan Turing, grâce à qui on sait que l’on peut définir des nombres réels qui ne sont pas calculables. Wigderson a souligné qu’aujourd’hui encore on est loin de comprendre parfaitement le lien entre preuve et calculabilité. Ce qui est « calculable par des algorithmes finis » est-il équivalent à ce qui est « prouvable par des algorithmes finis » ? Là encore, un théorème montre que non. L’orateur a bien sûr évoqué la fameuse conjecture questionnant l’équivalence des classes de complexité P (les problèmes que l’on peut résoudre en temps polynomial) et NP (ceux dont on peut vérifier la solution en temps polynomial). La question de savoir si oui ou non P égale NP reste ouverte (et mise à prix pour un million de dollars par l’Institut Clay).

Après avoir passé en revue l’essentiel des systèmes de preuve classiques et défini les caractéristiques d’un vérificateur efficace, Wigderson en venait au cœur de son sujet. Puisque la nature offre une source illimitée d’aléa, pourquoi ne pas miser sur une vision probabiliste de la preuve ? Wigderson a ainsi introduit l’auditoire aux systèmes de preuve interactive, basés sur un échange de messages entre un prouveur et un vérificateur, qui interagissent aussi longtemps que nécessaire pour qu’une solution juste soit trouvée, satisfaisant des propriétés de complétude (à terme, le vérificateur doit accepter la preuve correcte fournie) et de consistance (une preuve fausse doit être rejetée). Il a défini la classe IP, basée sur de tels systèmes de preuve interactive, où les problèmes sont vérifiables en temps polynomial et dont le vérificateur est une machine probabiliste. Puis la classe ZKIP, comme Zero-Knowledge Interactive Proof (preuve à divulgation nulle de connaissance), où le prouveur prouve au vérificateur qu’une proposition est vraie sans révéler d’autres informations que la véracité de cette proposition. NP est inclus dans ZKIP, autrement dit toute preuve peut être convertie en preuve ZK. L’impact des preuves ZK est énorme (des blockchains aux applications en physique nucléaire ou dans les tests ADN anonymes). Ces systèmes font cependant appel à la cryptographie. Comment s’en passer ? En inventant de nouveaux systèmes autorisant des prouveurs multiples. Wigderson nous a donc présenté la classe 2IP, basée sur des systèmes comportant deux prouveurs dialoguant avec un même vérificateur, classe qui contient IP et NP. D’autres systèmes suivaient, jusqu’à l’introduction de la classe PCP (Probabilistically Checkable Proofs, les preuves vérifiables en probabilité), où le vérificateur (probabiliste) fonctionne en ne lisant qu’un fragment de la démonstration.

Ces systèmes probabilistes ont montré leur efficacité et même leur supériorité sur des systèmes s’appuyant sur des machines déterministes, avec des applications en informatique, en mathématiques, dans le champ conceptuel, en optimisation, etc. On sait aujourd’hui que toute preuve peut être convertie en preuve PCP de manière efficace, ce qui présente un intérêt conséquent sur la vérification de très longues démonstrations.

En dernière partie d’exposé, Wigderson nous emmenait encore plus loin. Plus vertigineux que la preuve interactive probabiliste : la preuve interactive quantique ! Ici, l’idée est d’utiliser les gigantesques potentialités de l’informatique quantique (en particulier ses capacités de calcul sans commune mesure avec celles des machines classiques) avec des systèmes de type IP où les vérificateurs sont cette fois des algorithmes quantiques efficaces : voilà donc les classe IP* ou encore MIP* (pour des systèmes à prouveurs multiples). Encore un vaste champ de réflexion, en lien étroit avec la physique, et dans lequel des avancées stupéfiantes ont déjà été réalisées, laissant présager que bien des plafonds théoriques seront amenés à être brisés à l’avenir.

Fidèle à lui-même, Avi Wigderson a terminé son exposé en invitant l’auditoire à lire son livre, où tout ceci est dûment expliqué… livre pour lequel il recommande de ne pas débourser un centime, le PDF de celui-ci étant en accès libre sur son site : https://www.math.ias.edu/avi/book !