💻 computer science

A proof complexity conjecture and the Incompleteness theorem

Cet article établit l'incomplétude de certaines théories formelles via une fonction de temps polynomial étirant les entrées, et démontre qu'au moins l'une des trois hypothèses suivantes doit être vraie : l'absence de système de preuve propositionnel p-optimal, la séparation des classes de complexité $E$ et $P/poly$, ou l'existence d'une fonction étirant les entrées en temps sous-exponentiel dont l'image intersecte tous les ensembles NP infinis.

Auteurs originaux : Jan Krajicek

Publié 2026-02-16

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Jan Krajicek

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ Le Grand Mystère : Peut-on tout prouver ?

Imaginez que vous êtes un détective (un mathématicien) qui cherche à résoudre tous les mystères du monde. Vous avez un manuel de règles très strict (une théorie mathématique) pour vérifier si une affirmation est vraie ou fausse.

L'article de Krajíček pose une question fondamentale : Ce manuel de règles est-il assez puissant pour prouver absolument tout ce qui est vrai ?

La réponse, selon ce papier, est un grand NON. Et voici pourquoi, avec une histoire de "machine à étirer".

🧵 La Machine à Étirer (La Fonction $g_T$ )

Imaginons que nous créions une machine spéciale, appelons-la G.

Son travail : Elle prend un morceau de tissu (une suite de chiffres binaires, comme 0101) et elle le coupe, puis elle ajoute un petit bout de tissu supplémentaire.
Le résultat : Si vous lui donnez un tissu de 10 cm, elle vous en rend un de 11 cm. Elle "étire" toujours la matière d'un centimètre.

C'est ce qu'on appelle une fonction qui "étire d'un bit".

Le problème :
Même si cette machine est très rapide et très intelligente, elle ne peut pas fabriquer tous les tissus possibles de 11 cm. Il y aura toujours des motifs de 11 cm que la machine ne peut pas créer.

🚧 Le Mur de l'Incomplétude (Le Théorème de Gödel)

L'auteur utilise cette machine pour prouver un vieux secret découvert par Gödel (le théorème de l'incomplétude).

Voici l'analogie :

Supposons que votre manuel de règles (la théorie $T$ ) soit parfait et qu'il puisse prouver tout ce qui est vrai.
Si c'est le cas, notre machine $G$ devrait être capable de fabriquer n'importe quel motif de tissu, même ceux qui semblent impossibles.
Mais mathématiquement, on sait que cette machine laisse toujours des trous (des motifs qu'elle ne crée pas).
Conclusion : Puisque la machine laisse des trous, cela signifie que notre hypothèse de départ était fausse. Le manuel de règles ne peut pas prouver tout ce qui est vrai. Il y a toujours des vérités qui échappent à la logique du manuel.

C'est comme si vous aviez un dictionnaire parfait, mais qu'il y avait toujours un mot nouveau que vous ne pouviez pas définir avec les mots déjà présents.

🎲 Le Pari sur le Futur (Le Problème Ouvert)

L'auteur laisse une question en suspens (un "problème ouvert") :

"Est-il possible que cette machine $G$ soit si intelligente qu'elle touche à tous les types de tissus complexes (les ensembles NP) ?"

Si la réponse est OUI, cela signifierait que le monde informatique est beaucoup plus étrange que nous le pensons : cela prouverait qu'il existe des problèmes que les ordinateurs ne pourront jamais résoudre efficacement, même avec des milliards d'années de calcul.

🧩 La Version "Petite" (Logique Propositionnelle)

Dans la deuxième partie de l'article, l'auteur descend du ciel des mathématiques pures pour parler des ordinateurs réels (la logique propositionnelle). Il dit :

"Si nous ne pouvons pas trancher la question précédente, alors au moins l'une de ces trois choses doit être vraie :"

Le Manuel Idéal n'existe pas : Il n'existe pas de "super-méthode" unique pour vérifier les preuves mathématiques qui soit la plus rapide possible pour tout le monde. C'est comme dire qu'il n'y a pas de "marteau parfait" qui sert à tout.
L'Ordinateur a des Limites Physiques : Il y a des problèmes si complexes que même un ordinateur avec une puissance de calcul infinie (dans un sens théorique) ne pourrait pas les résoudre en utilisant juste un peu de mémoire.
Le Super-Générateur Existant : Il existe une fonction (une machine) qui est rapide, qui étire les données, et qui réussit à toucher tous les motifs complexes possibles. Si cette machine existe, alors les mathématiques et l'informatique sont dans un état de chaos fascinant où certaines énigmes sont intrinsèquement insolubles.

🎯 En Résumé

Ce papier est une aventure intellectuelle qui utilise une machine à étirer des données pour nous rappeler deux choses :

La vérité est plus grande que la preuve : Il y aura toujours des vérités mathématiques que nos règles ne pourront jamais capturer (c'est le théorème de Gödel).
L'informatique a des limites : Soit nos méthodes de vérification sont imparfaites, soit il existe des problèmes qui résistent à toute forme de calcul rapide.

L'auteur ne nous donne pas la réponse finale, mais il nous montre que le mystère est réel et que, quoi qu'il arrive, l'univers des mathématiques restera toujours un peu plus grand que notre capacité à le décrire.

Résumé Technique

1. Problématique et Contexte

L'article s'attaque à une vieille conjecture de la théorie de la complexité des preuves : l'existence d'un générateur de preuves difficile pour tous les systèmes de preuve.
Plus formellement, la conjecture postule l'existence d'une fonction calculable en temps polynomial ( $p$ -time) $g : \{0, 1\}^* \to \{0, 1\}^*$ qui étire chaque entrée d'un bit (c'est-à-dire $|g(u)| = |u| + 1$ ) et dont l'image (range) intersecte tous les ensembles infinis de la classe NP.

Si une telle fonction existait, elle impliquerait que $NP \neq coNP$ . L'auteur explore le lien entre cette conjecture et le théorème d'incomplétude de Gödel, en proposant une construction basée sur la logique du premier ordre et en déduisant des conséquences pour la logique propositionnelle.

2. Méthodologie et Construction

L'auteur développe deux constructions principales : une dans le cadre de la logique du premier ordre et une version propositionnelle.

A. Construction Logique du Premier Ordre ( $g_T$ )

Cadre théorique : L'auteur utilise la théorie $S^1_2$ de Buss, une théorie arithmétique faible capable de formaliser la syntaxe de la logique du premier ordre et de définir la hiérarchie polynomiale.
Définition de la fonction $g_T$ : Pour une théorie $T$ $T$ (sound, $p$ $p$ -time, contenant $S^1_2$ $S_{2}^{1}$ ), la fonction $g_T$ $g_{T}$ prend une entrée $u$ $u$ et procède comme suit :
1. Elle cherche un sous-mot préfixe de $u$ qui encode une formule $\Phi$ de la théorie avec une variable libre, de taille logarithmique par rapport à $u$ .
2. Elle génère une série de sentences $\Phi_w$ (basées sur $\Phi$ et des chaînes binaires $w$ ) qui affirment l'existence d'une borne au-delà de laquelle les mots commençant par $w$ ne satisfont pas $\Phi$ .
3. Elle recherche une preuve dans $T$ de taille logarithmique pour ces sentences.
4. Si une preuve est trouvée pour toutes les $w$ , elle sort une chaîne de zéros. Sinon, elle sort la première $w_0$ pour laquelle aucune preuve n'a été trouvée, concaténée au reste de l'entrée.
Propriété clé : Si $T$ est complète et sound, l'image de $g_T$ intersecterait tout ensemble infini définissable dans la théorie. Comme le complément de l'image est infini et définissable, cela crée une contradiction, prouvant ainsi l'incomplétude.

B. Version Propositionnelle et Complexité
L'auteur adapte cette construction au cadre propositionnel pour éviter l'incomplétude directe et se concentrer sur les bornes inférieures de la taille des preuves.

Il utilise une traduction canonique des formules $\Pi^b_1$ en formules propositionnelles tautologiques ( $\phi_{n,w}$ ).
Il suppose l'échec de deux hypothèses fortes (l'existence d'un système de preuve $p$ -optimal et l'inclusion $E \subseteq P/poly$ ) pour construire une fonction $h$ .
La fonction $h$ cherche des preuves dans un système de preuve $P$ en énumérant des circuits booléens de petite taille dont la table de vérité sert de preuve candidate.

3. Résultats Principaux

Théorème d'Incomplétude (Corollaire 2.3)
En appliquant la construction de $g_T$ à l'ensemble complémentaire de son image, l'auteur redémontre le Premier Théorème d'Incomplétude de Gödel : Aucune théorie $T$ sound, calculable en temps polynomial et contenant $S^1_2$ ne peut être complète.

Mécanisme : Pour toute définition $\Phi$ d'un ensemble infini, il existe une sentence vraie $\Phi_w$ qui n'est pas prouvable dans $T$ .

Théorème Propositionnel (Théorème 3.1)
L'auteur établit que au moins l'une des trois affirmations suivantes doit être vraie :

Absence de système optimal : Il n'existe pas de système de preuve propositionnel $p$ -optimal (ce qui équivaut à l'absence d'algorithme de recherche de preuves temporellement optimal).
Séparation de classes de complexité : $E \not\subseteq P/poly$ (la classe des problèmes résolubles en temps exponentiel linéaire n'est pas contenue dans les circuits de taille polynomiale).
Existence d'un générateur difficile : Il existe une fonction $h$ $h$ qui :
- Étire chaque entrée d'un bit.
- Est calculable en temps sous-exponentiel ( $2^{O((\log n)^{\log \log n})}$ ).
- Dont l'image intersecte tous les ensembles infinis de NP.

4. Contributions Clés

Lien Incomplétude/Complexité : L'article fournit une nouvelle perspective sur le théorème de Gödel en le reformulant via la complexité des preuves et les générateurs de nombres pseudo-aléatoires.
Construction Unifiée : Il propose une construction unifiée ( $g_T$ et $h$ ) reliant la logique du premier ordre (incomplétude) et la logique propositionnelle (complexité des preuves).
Résolution Conditionnelle : Il ne prouve pas directement la conjecture du générateur, mais montre que son échec impliquerait soit l'existence d'un système de preuve optimal, soit l'effondrement de la hiérarchie de complexité ( $E \subseteq P/poly$ ).
Problème Ouvert : L'auteur laisse ouverte la question de savoir si, pour une théorie $T$ spécifique, la fonction $g_T$ satisfait la conjecture (c'est-à-dire si son image intersecte tous les ensembles NP infinis). Une réponse affirmative impliquerait $NP \neq coNP$ .

5. Signification et Impact

Ce travail est significatif car il :

Renforce le lien entre les limites fondamentales de la logique (Gödel) et les limites computationnelles (complexité des preuves).
Éclaire la recherche de systèmes de preuve optimaux : Il montre que l'existence d'un tel système est liée à des questions profondes sur la puissance des circuits booléens ($P/poly$) et la complexité temporelle ( $E$ ).
Propose une voie alternative : Au lieu de chercher directement à prouver $NP \neq coNP$ , il suggère d'étudier les propriétés des générateurs de preuves et leur intersection avec les ensembles NP. Si un tel générateur existe (cas 3 du théorème 3.1), cela résoudrait la conjecture de complexité des preuves.

En résumé, Krajíček démontre que la difficulté à prouver l'incomplétude ou à séparer les classes de complexité est intrinsèquement liée à la capacité d'un système formel à "couvrir" (intersecter) tous les ensembles NP via une fonction de stretching.