Chapitre 8. P contre NP (II) : le mur, le compte et le prix

Le chapitre 7 a établi que toutes les séparations connues ont été payées par un tiers, et que le pas qui reste bute sur un mur nommé, les preuves naturelles. Ce chapitre, tiré de la pièce transversale d’octobre 2026, examine ce mur et ce qu’il est fait. Il montre que l’hypothèse qui fonde le mur contient déjà la séparation ; que les bits dits pseudo-aléatoires d’un générateur par repliement sont exactement le compte des tours jeté par le pli ; que la méthode qui a fondé la complexité (le compte de Shannon) a remplacé la relation nommée par un tirage ; que toutes les fermetures faciles de Schaefer sont des chiffres d’un compte, à deux ou à trois bits, et que sous deux conditions simples la retenue et le chiffre du compte de trois décident seuls de la frontière ; que connaître le compte ne donne pas l’adresse ; et enfin que l’énoncé du prix pose la question du tout ou rien, alors que le réel se règle par un prix adressé : la question que l’énoncé ne pose pas est « qui paie ». Chaque compte est refait en annexe D.

L’auteur a posé la question le 12 octobre 2026 :

« C’est local-global. » On peut tout régler globalement en sacrifiant des contraintes ; localement, les contraintes doivent être acceptées, sinon viennent le mécontentement, le blocage, l’inflammation. « La réponse est dans le local et sa borne de contraintes, sacrifices et bénéfices. » « La contrainte est duelle, et surtout la perception. » « Le prix est duel. »

et il en a donné l’image : un joueur préférerait jouer avec un autre, et le trio local s’en porterait mieux, mais l’entraîneur refuse, parce que cela affaiblirait les trois trios offensifs.

8.1 Ce qui manque : le tiers

[8.1] Th. La porte ET sur n bits. Dans {0, 1}ⁿ, la pré-image de 0 par x₁ ∧ x₂ compte 3 × 2^{n−2} points. Ce nombre n’est jamais une puissance de 2 ; elle n’est donc ni un sous-groupe ni une classe affine de {0, 1}ⁿ, qui ont toutes 2ᵏ éléments (vérifié pour n = 2 à 20 ; voir [7.4]).

Ce qui manque est le tiers : chaque séparation obtenue a reçu une restriction ou un oracle venus du dehors ([7.9]), et le problème nu n’en fournit aucun.

8.2 Le mur est fait de la séparation

[8.2] F. Le mur des preuves naturelles (Razborov et Rudich, 1997). Une preuve est dite naturelle si elle repose sur une propriété des tables de vérité qui est constructive et large. Aucune preuve naturelle ne peut établir des bornes inférieures de circuits assez fortes pour séparer P de NP, si des fonctions pseudo-aléatoires existent. Une fonction pseudo-aléatoire est un objet calculé, entièrement déterminé par sa graine, qu’aucun test polynomial ne distingue d’un tirage ; le mur demande en outre une dureté quantitative, de type 2^{nε}, plus forte que la seule résistance aux tests polynomiaux.

[8.3] Th. L’hypothèse du mur contient déjà la séparation. L’existence de fonctions pseudo-aléatoires entraîne celle de fonctions à sens unique, laquelle entraîne P ≠ NP.

Démonstration. Une famille de fonctions pseudo-aléatoires donne un générateur pseudo-aléatoire, et tout générateur est une fonction à sens unique (Goldreich, Foundations of Cryptography, 2001, chapitre 3). Si P = NP, toute fonction calculable en temps polynomial s’inverse en temps polynomial, puisque trouver un antécédent est un problème de NP ; il n’existe alors aucune fonction à sens unique. C’est un fait de la littérature, connu des spécialistes.

Le mur qui arrête les preuves naturelles n’existe donc que dans un monde où la réponse est déjà la séparation. « Il ne dit pas que la séparation est fausse ; il dit qu’une certaine langue ne peut pas l’écrire. »

8.3 Le pseudo-aléatoire est le compte des tours jeté

[8.4] Th. Les bits du pli sont l’écriture du compte des tours. Soit x₀ ∈ [0, 1) et le doublement replié x_{k+1} = 2x_k − b_{k+1}, où b_{k+1} ∈ {0, 1} est la partie entière de 2x_k. Alors le compte des tours jetés après n pas est wₙ = ⌊2ⁿ x₀⌋ = Σ_{k=1}^{n} b_k 2^{n−k} : les bits sortis par le pli sont exactement l’écriture du compte des tours. Avec ce compte, x₀ = (xₙ + wₙ)/2ⁿ, sans reste ; sans lui, la position xₙ a 2ⁿ antécédents.

Démonstration. Par récurrence, 2ⁿ x₀ = wₙ + xₙ avec 0 ≤ xₙ < 1. Le pas : 2^{n+1} x₀ = 2(wₙ + xₙ) = 2wₙ + b_{n+1} + x_{n+1}, d’où w_{n+1} = 2wₙ + b_{n+1} : l’écriture binaire de wₙ est la suite des bits sortis.

Calculs montrés. Pour x₀ = 1/3, les tours jetés sont 0, 0, 1, 2, 5, 10, 21, 42, 85 (n = 0 à 8), c’est-à-dire ⌊2ⁿ/3⌋, et chacun double le précédent en ajoutant le bit sorti ; la remontée se fait sans reste, et sans les tours la position après 8 pas a 256 antécédents. Pour x₀ = 1/1 000 003, le pli sort 4000 bits, dont 1952 uns, équilibrés à 2,4 % près, et la suite se rejoue à l’identique ; ces bits sont, chiffre pour chiffre, la partie entière de 2⁴⁰⁰⁰/1 000 003.

[8.5] L. Le pseudo-aléatoire est une suite déterminée dont on n’a pas le compte (M3). Ce que l’outil appelle pseudo-aléatoire est une suite entièrement déterminée dont le lecteur n’a pas le compte des tours (M3). Le mur de Razborov et Rudich dit qu’une propriété lue sur la table entière ne voit pas ce compte. [8.4] établit la réversibilité quand le registre est en main, et elle dit la taille de ce registre : n bits, exactement ce qu’il faut pour distinguer 2ⁿ antécédents, et pas un de moins. Elle ne dit pas le coût d’obtenir le registre à partir de la seule position : c’est la question cryptographique, et elle reste ouverte. Un générateur presque équilibré n’établit pas l’indistinguabilité ; il montre seulement de quoi elle est faite. C’est aussi la lecture de la cryptographie à clé publique de la carte du chapitre 6 : la sécurité tient au compte des tours jeté par le repliement.

[8.6] Chantier. Information, registre et reconstruction. Suivre ensemble l’information conservée, la taille du registre et le coût de sa reconstruction.

8.4 Où la piste s’est perdue

[8.7] F. Le compte de Shannon (1949) et la borne explicite (2022). Shannon démontre que presque toutes les fonctions booléennes de n variables exigent des circuits de taille de l’ordre de 2ⁿ/n. La preuve compte : il y a 2^{2ⁿ} fonctions et beaucoup moins de petits circuits. Pour n = 20, les circuits de moins de 30 985 portes ne peuvent pas calculer toutes les fonctions. La difficulté est établie pour la fonction typique, jamais pour une fonction nommée. Soixante-quinze ans plus tard, la meilleure borne inférieure connue pour une fonction explicite de NP est d’environ 3,1n portes (Li et Yang, 2022).

Calcul montré. En majorant le nombre de circuits à s portes par (16 (n + s)²)ˢ (chaque porte choisit l’une des 16 fonctions de deux bits et deux entrées parmi n + s fils), ce nombre reste sous 2^{2²⁰} = 2^{1 048 576} tant que s × log₂(16 (20 + s)²) < 1 048 576, c’est-à-dire jusqu’à s = 30 985.

[8.8] L. La méthode qui a fondé le domaine est celle qui l’empêche de conclure. La question de Gödel à von Neumann (lettre du 20 mars 1956) portait sur un objet nommé, la recherche d’une preuve. Sept ans plus tôt, le compte de Shannon avait remplacé la relation nommée par un tirage dans l’ensemble des fonctions : la difficulté était devenue une propriété de « presque toutes », c’est-à-dire de l’instrument (M3). Le mur des preuves naturelles est l’ombre exacte de ce compte : il interdit les propriétés larges, celles qui valent pour presque toutes les fonctions. « La méthode qui a fondé le domaine est celle qui l’empêche de conclure. La piste se retrouve en revenant à la relation nommée. »

8.5 Les deux lectures sont les deux chiffres d’un compte

[8.9] Th. Le compte de trois bits : la retenue et le chiffre. Pour trois bits a, b, c, avec maj la majorité et min = a ⊕ b ⊕ c la minorité, a + b + c = 2 maj(a, b, c) + min(a, b, c). La majorité est la retenue du compte, la minorité en est le chiffre. (Vérifié sur les huit triplets : par exemple 1 + 1 + 0 = 2 × 1 + 0 et 1 + 1 + 1 = 2 × 1 + 1.)

[8.10] F. Les fermetures de Schaefer, et leur extension. Un problème de satisfaction booléenne est dans P si ses relations ferment sous l’une des opérations suivantes : une constante, le ET, le OU, la majorité, la minorité ; sinon il est NP-complet (Schaefer, 1978, sous sa forme par les opérations de fermeture). Le résultat s’étend à tout domaine fini (Bulatov, 2017 ; Zhuk, 2017, publié en 2020). Les relations fermées par la majorité sont celles de 2-SAT ; celles fermées par la minorité sont les systèmes linéaires sur {0, 1}.

[8.11] Th. Le compte de deux bits. Pour deux bits, a + b = 2 (a ∧ b) + (a ⊕ b) et a + b = (a ∨ b) + (a ∧ b). Le ET est la retenue du compte de deux ; le OU en est la somme moins la retenue.

[8.12] L. Toutes les fermetures de Schaefer sont des chiffres d’un compte. Par [8.9] et [8.11], toutes les fermetures non triviales de Schaefer sont des chiffres d’un compte : la majorité et la minorité sont la retenue et le chiffre du compte de trois ; le ET et le OU sont ceux du compte de deux (les contraintes de Horn gardent la retenue à deux). La minorité est l’addition dont la retenue est jetée : c’est le pli qui fait du 2 un 0, la congruence selon 2.

[8.13] Th. Le recensement des relations sans pôles. En arité 3, sur les 63 relations non vides qui ne contiennent ni 000 ni 111 (les deux pôles), 24 ferment par la majorité et la minorité, 24 par la majorité seule, 0 par la minorité seule, 15 par aucune des deux. En arité 4, sur les 16 383 relations sans pôles : 168, 1472, 21 et 14 722, dont 4 ferment encore par le ET et 4 par le OU, par exemple x₁ ∧ (¬x₂ ∨ ¬x₃ ∨ ¬x₄).

[8.14] Th. Théorème de la frontière. Soit R une relation booléenne non vide sans les deux pôles et sans position figée (chaque coordonnée prend les deux valeurs dans R). Alors R ne ferme ni par une constante, ni par le ET, ni par le OU ; et le problème de satisfaction à contraintes R est polynomial si R ferme par la majorité ou par la minorité, NP-complet sinon.

Démonstration. Si R fermait par le ET, le ET de toutes ses lignes serait 0…0, puisque chaque coordonnée prend la valeur 0 quelque part ; ce pôle est exclu. De même pour le OU et 1…1. Les constantes sont exclues par l’absence des pôles. Il reste, dans la dichotomie de Schaefer, la majorité (cas bijonctif) et la minorité (cas affine). Recensement : en arité 4, 15 565 relations vérifient les hypothèses : 34 ferment par les deux, 1068 par la majorité seule, 13 par la minorité seule, 14 450 par aucune, et aucune par le ET ou le OU.

[8.15] L. Trois ne rentre pas dans deux parce que 3 = 2 · 1 + 1. Il faut la retenue et le chiffre pour porter trois, et une porte booléenne n’en rend qu’un. Une relation facile survit à la perte d’une moitié du compte, à deux ou à trois ; une relation dure n’en garde aucun. Une position figée est un local dont le sacrifice est déjà fait ; sans elle, la frontière se lit sur le seul compte de trois ([8.14]).

8.6 Le compte sans l’adresse

[8.16] Th. Le compte dit combien, non qui. Les configurations 100, 010, 001 ont le même compte, 1, la même retenue, 0, et le même chiffre, 1. Pour trois bits, les comptes 0, 1, 2, 3 sont portés par 1, 3, 3, 1 configurations.

[8.17] F. 1-dans-3 SAT est NP-complet. Le problème où chaque contrainte impose exactement un 1 parmi trois variables est NP-complet (Schaefer, 1978), alors que le compte y est connu d’avance et partout égal à 1.

[8.18] L. La difficulté est entièrement dans l’adresse. Le compte est localement fixé ; ce qu’il faut trouver est une attribution des adresses compatible d’une contrainte à l’autre. La difficulté est entièrement dans l’adresse.

8.7 La largeur

[8.19] F. La largeur de résolution. Dans le système de la résolution, une réfutation combine deux clauses en jetant une variable. Sa largeur est le plus grand nombre de littéraux tenus ensemble. Pour 2-CNF la largeur ne dépasse jamais 2, puisque deux clauses à deux littéraux résolvent en une clause à deux littéraux au plus (200 instances insatisfiables vérifiées dans la pièce source). Pour les pigeons (n + 1 pigeons, n trous) la largeur est d’ordre n, et toute réfutation a une taille d’au moins exp((w − w₀)²/n) (Haken, 1985 ; Ben-Sasson et Wigderson, 2001).

[8.20] L. La largeur est le compte des retenues tenues ensemble. Dans le modèle de la résolution, sa croissance force la taille. Ce modèle est lui-même une restriction, un tiers.

[8.21] Chantier. Lever la largeur hors du modèle de la résolution. C’est le pas que le chapitre 7 nomme C-1 ([7.26]).

8.8 La question qui manque : le prix est duel

L’énoncé du prix demande s’il existe une affectation qui satisfait toutes les contraintes. À chaque contrainte correspond un prix, la variable duale ; le problème côté affectations et le problème côté prix sont deux lectures d’une seule situation, et ils ferment ensemble quand leurs valeurs coïncident. L’écart entre les deux est l’écart de dualité.

[8.22] F. Paires et trios (König, 1931 ; Karp, 1972). Former des paires entre deux groupes (couplage biparti) est dans P, et la lecture par prix y est exacte : la valeur fractionnaire égale la valeur entière, pour toute instance (König, 1931). Former des trios à partir de trois groupes (couplage tridimensionnel) est NP-complet (Karp, 1972).

[8.23] Th. Trois trios : l’écart d’intégralité, et sa fermeture par un sacrifice. Soit trois trios qui se chevauchent deux à deux par un joueur : T₁ = (c₁, g₁, d₁), T₂ = (c₁, g₂, d₂), T₃ = (c₂, g₂, d₁). La lecture par prix donne 3/2, chaque trio pris à moitié, avec un prix de ½ sur trois joueurs (c₁, g₂, d₁), et l’écart de dualité linéaire est nul : fractionnaire et prix coïncident. La lecture entière donne 1 : l’écart de ½ est un écart d’intégralité, entre le fractionnaire et l’affectation réelle. Dès qu’un trio cède en entier, les deux lectures donnent 1, le prix se concentre sur un seul joueur et vaut 1, et tous les autres prix sont nuls : l’écart d’intégralité est nul.

Démonstration. Programme linéaire et écarts complémentaires (Kuhn et Tucker, 1951). Chaque joueur partagé porte la contrainte « la somme des parts des trios qui le contiennent ne dépasse pas 1 » : z₁ + z₂ ≤ 1 (c₁), z₂ + z₃ ≤ 1 (g₂), z₁ + z₃ ≤ 1 (d₁). La somme donne 2(z₁ + z₂ + z₃) ≤ 3, atteinte à ½ chacun ; deux trios entiers partagent toujours un joueur, donc l’entier vaut 1. Contrôle : sur des instances bipartites tirées par un générateur (60 refaites en annexe D, 295 dans la pièce source), l’écart d’intégralité est nul ; sur les trios, il vaut ½.

[8.24] Th. Les anneaux impairs. Soit 2r + 1 trios en anneau, chacun partageant un joueur avec chacun de ses deux voisins et aucun autre. Avec zᵢ la part du trio i, les contraintes sont zᵢ + zᵢ₊₁ ≤ 1 ; leur somme donne 2 Σ zᵢ ≤ 2r + 1, et chaque trio à moitié atteint r + ½. En entiers, on en joue exactement r. L’écart d’intégralité vaut ½ pour toute longueur impaire. Retirer un trio adressé ouvre l’anneau en chaîne de 2r trios, où fractionnaire et entier valent r. (Vérifié pour 3 à 11 trios.)

[8.25] L. Le certificat de NP est l’adresse de qui paie. La lecture fractionnaire, où chacun porte la moitié, est le prix étalé : personne n’a cédé, rien ne ferme, et le total ne correspond à aucune équipe réelle. Le coût global est ici l’écart d’intégralité, et non la valeur du problème, qui reste r : le sacrifice adressé ferme cet écart à zéro sans rien perdre du nombre de trios jouables ([8.24]) ; ce qui reste n’est pas un coût, c’est une adresse, celle de qui paie. « Le certificat de NP est cette adresse. Vérifier, c’est lire la liste de qui cède ; chercher, c’est la trouver. » La difficulté ne porte pas sur le coût, nul une fois localisé, mais sur la localisation.

[8.26] L. Thèse de l’auteur : le prix est duel. « La contrainte est duelle, et le prix l’est aussi. Le sacrifice doit être local, et alors le coût global est nul. Un local qui refuse son prix ne l’annule pas : il le garde, et l’écart revient par l’intérieur. »

8.9 La loi du cadre

[8.27] Th. L’échiquier est l’unique carré dont le bord est le nombre de ses liens. Pour un carré de n × n cases, le bord compte 4(n − 1) cases et les paires formées avec n éléments comptent n(n − 1)/2. Les deux nombres coïncident si et seulement si n = 8 : l’échiquier est l’unique carré dont le bord, 28 cases, est le nombre de ses liens, C(8, 2) = 28. Son intérieur compte 36 = 6² cases, et 64 = 28 + 36. Une case intérieure a 8 voisines ; une case du bord en a 3 (un coin) ou 5.

Démonstration. 4(n − 1) = n(n − 1)/2 donne (n − 1)(n − 8) = 0, donc n = 8 pour n ≥ 2.

[8.28] L. Le cadre est le prix adressé. Le carré de jeu porte à l’intérieur les parties, illimitées sous des règles fixes, et sur son bord les cases auxquelles des liens manquent, et qui tiennent le tout. « Le cadre est le prix adressé. » La cloche de Gauss est un carré sans bord : l’écart distribué à chaque case, aucune qui tienne. La loi du cadre en est l’inverse : le prix concentré sur les cases qui ferment, et le compte global soldé. « Le trio qui cède est une case qui passe au bord. »

8.10 Pourquoi c’était si difficile

[8.29] L. La langue suppose ce qu’elle cherche, puis s’interdit de le lire. Le problème nu demande une séparation sans tiers, et le seul outil connu pour certifier une difficulté, la suite qu’on ne distingue pas d’un tirage, est lui-même un pli qui jette les tours. La langue qui pose le problème suppose déjà ce qu’elle cherche à démontrer, puis s’interdit de le lire. Et l’énoncé pose la question du tout ou rien, « toutes les contraintes satisfaites », là où le réel se règle par un prix adressé : la question que l’énoncé ne pose pas est « qui paie ».

8.11 Objections et réponses

Objection. Que le mur des preuves naturelles suppose une hypothèse plus forte que P ≠ NP est connu des spécialistes. Réponse. Oui : [8.3] est un fait de la littérature. Ce que le corpus ajoute est la lecture de l’hypothèse elle-même ([8.4]) : le pseudo-aléatoire est le compte des tours jeté par un pli, ce qui désigne la propriété que le mur ne couvre pas, celle qui garde le rang.

Objection. La dualité linéaire et les écarts complémentaires sont classiques ; l’écart d’intégralité des trios aussi. Réponse. Oui, et ils sont cités comme faits. Ce qui est ajouté est la lecture : l’écart d’intégralité comme prix étalé, le certificat comme adresse du sacrifice, la famille des anneaux où un seul retrait ferme l’écart, et la question « qui paie » comme celle que l’énoncé du prix ne pose pas.

Objection. La majorité et la minorité ne suffisent pas à caractériser la frontière : des relations de Horn ferment par le ET sans fermer par l’une ni l’autre. Réponse. Exact, et le recensement le compte : 4 par le ET et 4 par le OU parmi les 14 722. Le ET et le OU sont les chiffres du compte de deux ([8.11]), et sous les hypothèses de [8.14] ils sont exclus, de sorte que la frontière se lit sur le compte de trois.

8.12 Conditions de réfutation

[8.30] L. Ce qui réfuterait les énoncés de ce chapitre. [8.9] serait réfuté par un triplet de bits qui ne le vérifie pas ; [8.27], par un n ≠ 8 avec 4(n − 1) = n(n − 1)/2 ; [8.14], par une relation sans pôle et sans position figée qui ferme par le ET ou le OU, ou par une relation sous ces hypothèses qui soit NP-complète en fermant par la majorité ou la minorité ; la lecture [8.25], par un problème NP-complet dont la lecture par prix serait exacte sur toute instance ; [8.24], par un anneau impair où un retrait ne ferme pas l’écart. La Prédiction datée P-2 ([7.29]) s’y ajoute : si le problème nu est résolu, il le sera dans le sens P ≠ NP.

8.13 Portée

Pour P contre NP, le corpus établit que le mur suppose la séparation, que toutes les fermetures de Schaefer sont des chiffres d’un compte et que, sans pôle ni position figée, le compte de trois décide seul de la frontière, que le compte connu ne donne pas l’adresse, que l’écart d’intégralité est nul pour les paires et vaut ½ pour tout anneau impair de trios, et que l’échiquier est le seul carré dont le bord est le nombre de ses liens. La séparation sur le problème nu reste à démontrer, et le corpus dit quelle question l’énoncé ne pose pas.