P est-il égal à NP ? Vérifier une solution est-il aussi difficile que la trouver ?
Résumé
Si P = NP, la plupart des problèmes réputés impossibles deviennent faciles — et la cryptographie moderne s'effondre. Personne ne sait trancher.
Équations
Reproduites exactement comme déposées. Elles font partie de ce qui est signé.
LaTeX
\mathrm{P} \overset{?}{=} \mathrm{NP}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
La preuve
✓Signature du club : valide
✓Contenu inchangé depuis le dépôt
✓Maillon de chaîne correct
✕Ancrage Bitcoin toujours pas confirmé après 5 jours — c'est anormal, et la preuve reste incomplète tant que ce n'est pas résolu
6122732520e0983d9670702b85391bd7d4fd80d15a0d8cf88c1988433704c029
0ef77feee55d84532f6843fb1d6987fc55e7c413b150b58c425899ecb5d5c7ca
Télécharger la preuve (.ots) Télécharger les octets signés
Vérifier vous-même, sans nous
Téléchargez les deux fichiers, puis : ots upgrade preuve.ots et ots verify preuve.ots -f octets-signes.txt avec le client officiel OpenTimestamps. La signature du club se vérifie avec la clé publique publiée sur /api/club/cle.
Comment citer ce dépôt
L'empreinte fait partie de la citation : elle permet à qui vous lit de vérifier que le dépôt cité est bien celui qu'il consulte.
Licence : Tous droits réservés — aucune réutilisation sans l'accord de l'auteur
Horizon Builder, « P est-il égal à NP ? Vérifier une solution est-il aussi difficile que la trouver ? », THOTH — Horizon Builder, dépôt n°2, 2026-09-09, SHA-256 6122732520e0983d9670702b85391bd7d4fd80d15a0d8cf88c1988433704c029, https://horizonbuilder.space/registre/2BibTeX
@misc{thoth2,
author = {Horizon Builder},
title = {P est-il égal à NP ? Vérifier une solution est-il aussi difficile que la trouver ?},
howpublished = {THOTH --- Horizon Builder, dépôt no. 2},
year = {2026},
note = {SHA-256 6122732520e0983d9670702b85391bd7d4fd80d15a0d8cf88c1988433704c029},
url = {https://horizonbuilder.space/registre/2}
}Vous avez une piste ?
Déposez votre solution, même partielle : elle sera signée à votre nom, datée, et rattachée à ce problème. Une piste qui ne marche pas mais qu'on peut lire vaut mieux qu'une idée que personne ne verra jamais.
Proposer une solution →Ce sont de simples liens : aucun script de réseau social n'est chargé sur cette page.
Commentaires
Aucun commentaire pour l'instant.
Les commentaires sont réservés aux membres du club. Demander ma carte de membre →