Calcul et complexité

Que peuvent vraiment faire les ordinateurs — et que ne peuvent-ils pas ?

Niveau Débutant — langage simple, sans maths

Les ordinateurs paraissent inarrêtables — ils font atterrir des fusées, écrasent les grands maîtres aux échecs, peignent des scènes photoréalistes à partir d'une phrase. Voici donc une vraie secousse : il existe des problèmes qu'aucun ordinateur, si rapide, énorme ou astucieusement codé soit-il, ne résoudra jamais. Non parce que nous n'avons pas encore bâti la bonne machine, mais parce que c'est mathématiquement impossible, point.

Alan Turing le prouva en 1936 — avant même que les vrais ordinateurs existent. Aucun programme ne peut être écrit qui décide de façon fiable si un programme donné finira un jour ou tournera pour toujours. Cela s'appelle le problème de l'arrêt, et il est prouvablement insoluble. Le tour de Turing fut de la pure logique : si un tel vérificateur existait, tu pourrais le pointer sur lui-même et fabriquer une contradiction, exactement comme la phrase « Cet énoncé est faux. »

Au-delà de l'impossible se tient la question du simplement difficile. Trier une liste prend des millisecondes ; trouver le plus court circuit à travers 1 000 villes semble exiger d'essayer un nombre ahurissant de combinaisons, sans espoir même pour un superordinateur. La plus grande question ouverte de l'informatique — et l'un des grands problèmes non résolus de toutes les mathématiques — est de savoir si ces problèmes difficiles sont vraiment difficiles, ou si nous avons simplement été trop lents à repérer un raccourci. C'est P vs NP, et il y a un prix de 1 000 000 de dollars qui attend celui qui le tranchera.

Machines de Turing, décidabilité et le zoo de la complexité

Niveau Élève — les équations essentielles

Une machine de Turing est le calcul réduit à l'os : un ruban infini, une tête qui lit et écrit une case, et une poignée d'états avec des règles \(\delta(\text{état}, \text{symbole}) \to (\text{état}', \text{symbole}', \text{mouvement})\). Elle paraît absurdement primitive, et pourtant la thèse de Church-Turing soutient que tout ce qui est calculable est calculable par l'une d'elles. Et une seule machine de Turing universelle, à qui l'on donne la description de n'importe quelle autre, peut l'imiter parfaitement — la graine théorique de chaque ordinateur généraliste que tu aies jamais utilisé.

Le problème de l'arrêt de Turing tombe par diagonalisation. Suppose qu'un décideur \(H(M, w)\) puisse toujours dire si la machine \(M\) s'arrête sur l'entrée \(w\). Construis un trouble-fête \(D(M)\) qui exécute \(H(M, M)\) puis fait l'opposé — boucle si \(H\) dit « s'arrête », s'arrête si \(H\) dit « boucle ». Maintenant donne à \(D\) sa propre description : \(D(D)\) s'arrête exactement quand il ne le fait pas. Contradiction, donc \(H\) ne peut exister. Le théorème de Rice généralise les dégâts : toute question non triviale sur ce que fait un programme est indécidable, ce qui est pourquoi le contrôle de bugs automatique parfait est hors de portée.

Parmi les problèmes qui sont résolubles, on trie par coût. P est tout ce qui est décidable en temps polynomial ; NP est tout ce dont la réponse, une fois devinée, peut être vérifiée en temps polynomial — Sudoku, coloration de graphes, factorisation. Un problème est NP-complet s'il est dans NP et que tout autre problème NP s'y réduit, donc il est aussi difficile que toute la classe d'un coup. Cook et Levin (1971) prouvèrent que la satisfiabilité booléenne (SAT) est un tel problème, et des milliers de problèmes quotidiens l'ont depuis rejoint. Résous-en un seul efficacement et tu as prouvé \(P = NP\) — et tu les as tous résolus.

Complexité des circuits, calcul randomisé et les limites de la preuve

Niveau Expert — profondeur mathématique complète

01P vs NP comme question sur la taille des circuits

Un angle prometteur sur \(P\) vs \(NP\) le reformule en matériel. Tout calcul peut être disposé comme un circuit booléen — un graphe de portes ET, OU et NON — et son coût est le nombre de portes. Tout ce qui est dans \(P\) a des circuits de taille polynomiale, donc si tu pouvais prouver qu'un problème \(NP\) nécessite superpolynomialement de portes, tu séparerais les classes. Le plan est propre ; l'exécution s'est révélée brutale.

02Les fonctions difficiles existent — on ne peut juste pas en désigner une

Curieusement, nous savons que les fonctions difficiles sont partout. Un simple argument de dénombrement (Shannon) montre que presque toute fonction booléenne sur \(n\) bits nécessite un circuit de taille \(\Omega(2^n/n)\) — astronomiquement grand — donc la vaste majorité des fonctions sont difficiles. Le hic est que l'argument est non constructif : il prouve que les fonctions difficiles abondent sans en nommer une seule. Pour des fonctions explicites dans \(NP\), les meilleures bornes inférieures que quiconque ait prouvées restent près de \(\Omega(n \log n)\), une distance risible de l'exponentiel. Nous sommes entourés de problèmes difficiles et ne pouvons en prouver difficile presque aucun.

03La barrière des preuves naturelles

Pire, il y a des preuves que les stratégies évidentes ne peuvent pas marcher. Razborov et Rudich (1994) montrèrent que toute preuve « naturelle » — constructive et applicable à la plupart des fonctions, comme le sont presque tous les arguments sur les circuits — si elle prouvait de fortes bornes inférieures, te livrerait aussi un algorithme pour casser les générateurs pseudo-aléatoires cryptographiques. Ainsi une preuve naturelle de \(P \ne NP\) détruirait les fonctions à sens unique mêmes que la cryptographie moderne suppose exister. Les outils qui semblent évidents sont prouvablement trop grossiers.

04Les autres murs : relativisation et algébrisation

Deux barrières de plus enserrent le domaine. La plupart des techniques classiques relativisent — elles marcheraient encore si chaque machine avait un oracle magique — et pourtant il existe des mondes à oracle où \(P = NP\) et d'autres où \(P \ne NP\), donc aucune preuve qui relativise ne peut trancher. Les méthodes algébriques qui résolurent \(IP = PSPACE\) esquivent cela mais heurtent la barrière ultérieure de l'algébrisation. Entre elles, trois barrières excluent essentiellement toute méthode que nous avons actuellement — ce qui est pourquoi une résolution nécessiterait une idée véritablement nouvelle, non une version plus affûtée d'une ancienne.

05Le hasard est-il vraiment nécessaire ?

Un fil différent demande si les lancers de pièce ajoutent une vraie puissance. BPP est ce que tu peux résoudre en temps polynomial en autorisant une petite erreur bilatérale, et pendant des décennies il sembla strictement plus riche que \(P\). La surprise (Impagliazzo-Wigderson, 1997) est que ce n'est probablement pas le cas : si des fonctions suffisamment difficiles existent, alors \(BPP = P\) et tout algorithme randomisé peut être dérandomisé. La difficulté, le méchant de l'histoire P-vs-NP, se révèle exactement ce qu'il faudrait pour rendre le hasard superflu.

06Preuves interactives et un choc de 2020

Laisse un vérifieur interroger un prouveur et la portée du calcul s'étend de façon stupéfiante. Shamir prouva \(IP = PSPACE\) : tout ce qui est résoluble en mémoire polynomiale peut être vérifié par conversation. Ajoute plusieurs prouveurs partageant un intrication quantique et cela explose jusqu'à \(MIP^* = RE\) (Ji et al., 2020) — toute la classe des problèmes récursivement énumérables, y compris les indécidables. Ce résultat n'a pas seulement sidéré les théoriciens de la complexité ; il trancha la conjecture d'immersion de Connes en algèbre des opérateurs pure, un rappel que la théorie du calcul atteint désormais les coins lointains des mathématiques.