P est-il égal à NP ? Vérifier une solution est-il aussi difficile que la trouver ?

Ce problème n'est pas de nous. Horizon Builder le pose ici pour qu'on y travaille, avec une date et une signature — pour que celui ou celle qui y apportera quelque chose puisse le prouver.

L'énoncé

P est la classe des problèmes qu'une machine résout en temps polynomial. NP est celle des problèmes dont une solution proposée se **vérifie** en temps polynomial. Toute solution vérifiable rapidement peut-elle aussi être trouvée rapidement ?

Pourquoi ça compte

Un sudoku rempli se vérifie en quelques secondes ; le remplir est une autre affaire. Cette asymétrie, si elle est réelle, est ce qui fait tenir toute la cryptographie à clé publique — donc les paiements, les signatures, cette page. Si P = NP avec un algorithme praticable, tout cela tombe. Si P ≠ NP, on aura démontré qu'une limite existe et qu'on ne la franchira jamais.

Ce qu'on sait

• Cook et Levin ont montré en 1971 qu'il existe des problèmes NP-complets : les résoudre rapidement résoudrait tout NP rapidement. La satisfiabilité booléenne en est un.
• Des milliers de problèmes concrets sont NP-complets — voyageur de commerce, coloration de graphes, sac à dos.
• Deux barrières méta-mathématiques sont démontrées : la relativisation (Baker, Gill, Solovay, 1975) et les preuves naturelles (Razborov, Rudich, 1994). Elles disent que la plupart des techniques connues **ne peuvent pas** trancher.

Ce qui compterait comme progrès

Une borne inférieure de circuit pour un problème explicite de NP. Une technique qui échappe aux deux barrières ci-dessus. Ou, plus modestement, une séparation entre deux classes plus petites.

Pour commencer

Clay Mathematics Institute : https://www.claymath.org/millennium-problems/

Contribuer

Déposez une solution — même partielle, même une piste qui échoue — avec le bouton « Proposer une solution » en bas de cette page. Elle sera signée à votre nom, datée, ancrée dans Bitcoin et rattachée à ce problème.

• une réduction, un cas particulier, une borne : ça compte
• un contre-exemple à une approche courante : ça compte aussi
• une objection argumentée à une solution déposée : ça compte encore