Les limites du calcul

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• expliquer pourquoi la question «tout problème admet-il un algorithme?» exige d'abord une définition formelle du mot «algorithme», et décrire le modèle de la machine de Turing (ruban, tête, états, table de transition);
• exécuter à la main une machine de Turing donnée par sa table de transition, écrire ses configurations successives, et expliquer ce qu'est une machine universelle;
• énoncer la thèse de Church–Turing, distinguer ce qu'elle affirme de ce qu'elle n'affirme pas, et dire pourquoi elle n'est pas un théorème;
• reconstruire de mémoire la démonstration par diagonalisation de l'indécidabilité du problème de l'arrêt, et énoncer précisément ce que ce résultat interdit et ce qu'il n'interdit pas;
• démontrer l'indécidabilité d'un problème par réduction depuis le problème de l'arrêt, et énoncer informellement le théorème de Rice;
• définir les classes $\mathsf{P}$ et $\mathsf{NP}$, la réduction polynomiale, la $\mathsf{NP}$-difficulté et la $\mathsf{NP}$-complétude, situer le problème ouvert $\mathsf{P}$ contre $\mathsf{NP}$ et dire ce que chaque réponse impliquerait.

Une question qu'il faut d'abord rendre précise

Les chapitres 2 à 4 ont construit des algorithmes et mesuré leur coût. Le chapitre 2 a introduit la notation $O(\cdot )$ et comparé un tri quadratique à un tri en $\Theta (n{\log }_{2}n)$; le chapitre 3 a montré comment «diviser pour régner» fait basculer une récurrence d'une classe dans une autre; le chapitre 4 a parcouru des graphes en temps linéaire en le nombre d'arêtes. À chaque fois, la question était: combien d'opérations?

Ce chapitre pose la question d'avant: y a-t-il un algorithme? Et, quand il y en a un: peut-il être rapide? Ce sont les deux limites du calcul. La première est absolue et définitive: certains problèmes parfaitement bien posés n'admettent aucun algorithme, ni aujourd'hui ni jamais, quelle que soit la machine. La seconde est, à l'heure où ces lignes sont écrites, une conjecture: on soupçonne très fortement que certains problèmes solubles n'admettent pas d'algorithme efficace, mais personne ne l'a démontré.

Pourquoi une définition informelle ne suffit pas

Le chapitre 2 a défini un algorithme comme «une suite finie d'instructions non ambiguës qui, sur toute entrée admissible, se termine et produit la bonne réponse». Cette définition est excellente pour écrire un algorithme. Elle est inutilisable pour démontrer qu'il n'en existe pas.

Imaginez que l'on veuille prouver: «aucun algorithme ne résout le problème $A$». Il faut raisonner sur l'ensemble de tous les algorithmes possibles. Or, tant que «instruction non ambiguë» n'est pas défini mathématiquement, cet ensemble n'est pas un objet mathématique et l'on ne peut rien en dire. C'est une situation analogue à celle de la géométrie: on ne peut pas démontrer qu'on ne sait pas trisecter un angle à la règle et au compas tant qu'on n'a pas dit exactement ce que «la règle et le compas» autorisent.

Le besoin était pressant. À la fin des années 1920, Hilbert et Ackermann posaient l'Entscheidungsproblem (problème de la décision): existe-t-il une procédure mécanique qui, recevant un énoncé de la logique du premier ordre, décide s'il est universellement valide? Pour répondre «non», il fallait d'abord dire ce qu'est une procédure mécanique. Trois définitions apparaissent presque en même temps, en 1936: le $\lambda$-calcul d'Alonzo Church, les fonctions récursives générales (Gödel, Herbrand), et la machine de Turing, publiée par Alan Turing dans un article intitulé On Computable Numbers, with an Application to the Entscheidungsproblem. Les trois définissent exactement la même classe de fonctions calculables. C'est ce modèle-là que nous suivons, parce que c'est le plus concret des trois: c'est une description de ce que fait une personne qui calcule avec un crayon et du papier.

Problèmes de décision

Pour parler proprement de calculabilité, on se restreint à une forme de problème particulièrement simple, qui ne perd presque rien en généralité.

Cette restriction est moins sévère qu'elle n'en a l'air. «Trier ce tableau» n'est pas un problème de décision, mais «le $k$-ième plus petit élément de ce tableau vaut-il $v$?» en est un, et un algorithme qui répond à toutes ces questions permet de reconstruire le tableau trié avec un surcoût polynomial. De même «quel est le plus court circuit passant par ces $n$ villes?» devient «existe-t-il un circuit de longueur au plus $B$?». On appelle cette transformation le passage à la version décision d'un problème d'optimisation; nous nous en servirons constamment dans la seconde moitié du chapitre.

Un point de vocabulaire important, sur lequel repose tout ce qui suit: comme une entrée est un mot fini, et comme un programme est lui aussi un texte fini, un programme peut être donné en entrée à un programme. Nous noterons $⟨P⟩$ le mot qui code le programme $P$ — son code source, si l'on veut, vu comme une suite de bits. C'est l'idée la plus féconde du chapitre.

La machine de Turing

Le modèle

Turing part de l'observation suivante: une personne qui calcule dispose d'une feuille de papier quadrillée, lit un symbole à la fois, écrit un symbole à la fois, déplace son attention d'une case vers la gauche ou vers la droite, et se trouve à chaque instant dans un «état d'esprit» pris dans un répertoire fini. Il ne reste qu'à formaliser.

Trois remarques. D'abord, tout est fini dans cette machine sauf le ruban: l'alphabet, l'ensemble des états, et donc la table $\delta$, qui n'a que $|Q|\times |\Gamma |$ lignes. Une machine de Turing est un objet fini, que l'on peut écrire sur une feuille — nous le ferons. Ensuite, le ruban infini n'est pas de la triche: on ne suppose pas une mémoire infinie disponible, on suppose qu'il y a toujours assez de mémoire, ce qui est l'idéalisation raisonnable si l'on veut étudier ce qui est calculable en principe. Enfin, il n'y a aucune instruction de haut niveau: pas d'addition, pas de boucle pour, pas de tableau. Tout cela devra être construit.

Une machine complète: le successeur binaire

Construisons une machine qui, recevant un entier naturel $n\ge 1$ écrit en binaire sur le ruban (bit de poids fort à gauche, tête sur ce bit), laisse sur le ruban l'écriture binaire de $n+1$.

La stratégie est celle de l'addition posée à la main: on va d'abord à la fin du nombre, puis on ajoute $1$ au dernier chiffre en propageant la retenue vers la gauche. Cela donne deux états de travail et un état d'arrêt:

• $q_0$: «je cherche la fin du nombre». Tant que je lis un chiffre, je le laisse tel quel et j'avance à droite. Quand je lis un blanc, j'ai dépassé la fin: je recule d'une case et je passe en $q_1$.
• $q_1$: «je propage la retenue». Si je lis $1$, alors $1+1=10$ en binaire: j'écris , je garde la retenue, je recule à gauche. Si je lis , alors sans retenue: j'écris et j'ai fini. Si je lis un blanc, c'est que tous les chiffres valaient : j'écris un de tête et j'ai fini.

La table de transition complète tient en six lignes:

L'explorateur ci-dessous exécute la même machine pas à pas, sur l'entier de votre choix. Regardez en particulier le readout «valeur lue sur le ruban»: il ne vaut $n+1$ qu'à la toute dernière étape.

Ce que ce modèle minuscule sait faire

Il est légitime de trouver ce modèle dérisoire. Il l'est en efficacité: un accès mémoire qu'un ordinateur fait en une instruction coûte à une machine de Turing autant de pas qu'il y a de cases à parcourir. Il ne l'est pas en puissance. On sait construire — et cela a été fait en détail dans la littérature — des machines de Turing qui additionnent, multiplient, comparent, copient un bloc de ruban, simulent des tableaux, des piles et des appels récursifs.

Mieux: les variantes du modèle n'y ajoutent rien.

Nous admettons ce théorème: chacune de ses parties se démontre par une simulation explicite, fastidieuse mais sans idée nouvelle (on code les $k$ rubans sur un seul en les entrelaçant, on remplace un symbole de $\Gamma$ par un bloc de $\lceil {\log }_2|\Gamma |\rceil$ bits, et ainsi de suite). Ce qu'il faut en retenir est que les simulations coûtent du temps — passer de $k$ rubans à un seul peut élever le nombre d'étapes au carré — mais rien de ce qui est calculable ne devient incalculable, ni l'inverse. Le cas non déterministe est à part et coûte bien davantage: nous y reviendrons au sujet de $\mathsf{NP}$.

La machine universelle: un programme est une donnée

Voici l'idée qui fait de la machine de Turing autre chose qu'une curiosité. Une machine $M$ est un objet fini: son alphabet, ses états et sa table de transition peuvent être écrits comme un mot fini sur $\{0,1\}$ — sa description, notée $⟨M⟩$. Rien n'empêche alors d'écrire ce mot sur le ruban d'une autre machine.

La construction, esquissée: $U$ garde sur son ruban trois zones — la description $⟨M⟩$, le ruban courant de $M$, et l'état courant de $M$. Une étape de $M$ se simule en lisant le symbole courant, en cherchant dans $⟨M⟩$ la ligne de $\delta$ qui correspond au couple (état, symbole), puis en appliquant ce que cette ligne dit. C'est long à écrire et il n'y a rien à comprendre de plus.

Il faut prendre la mesure de ce que cela signifie. En 1936, l'énoncé «il existe une machine unique, fixée une fois pour toutes, qui exécute n'importe quelle autre machine qu'on lui décrit» est une découverte mathématique. Aujourd'hui, c'est la description de l'objet posé sur votre bureau: un ordinateur est une machine universelle, un programme est une donnée qu'on lui fournit, et c'est pourquoi il n'y a pas besoin d'un appareil différent pour le traitement de texte et pour la messagerie. Les interprètes, les compilateurs, les machines virtuelles et les émulateurs sont tous des machines universelles au sens de Turing.

Deux conséquences immédiates, et elles vont dans des directions opposées:

• Positive: on peut écrire des programmes qui manipulent des programmes. Compilateurs, analyseurs statiques, vérificateurs de types, débogueurs, outils de test.
• Négative: on peut faire raisonner un programme sur lui-même. C'est exactement ce dont nous aurons besoin pour démontrer, dans la section sur l'arrêt, que certains de ces outils ne peuvent pas exister.

La thèse de Church–Turing

Nous avons maintenant une définition mathématique du calcul. Mais est-ce la bonne? Autrement dit: quand nous démontrerons que les machines de Turing ne savent pas faire quelque chose, aurons-nous démontré que le calcul ne sait pas le faire?

Ce qu'elle affirme, ce qu'elle n'affirme pas

Elle affirme: le modèle de Turing capture la notion intuitive de calcul mécanique. Elle a donc une valeur pratique immense, celle d'une licence de raisonnement: pour montrer qu'une fonction est calculable, il suffit d'en donner un algorithme en français, ou en pseudocode, ou en Python — inutile d'écrire la machine de Turing. Nous nous en servirons ainsi à partir de la section suivante.

Elle n'affirme pas, en revanche:

• rien sur l'efficacité. La thèse porte sur ce qui est calculable, pas sur le coût. L'énoncé selon lequel tout modèle raisonnable simule tout autre modèle raisonnable avec un surcoût seulement polynomial est une affirmation différente, appelée thèse de Church–Turing étendue (ou thèse de Cobham–Edmonds). Elle est bien plus fragile: le calcul quantique, si des machines de taille utile existaient un jour, la mettrait en difficulté pour certains problèmes, sans rien changer à la thèse originale;
• rien sur ce que l'univers physique peut faire. Que tout processus physique soit simulable par une machine de Turing est une hypothèse sur la physique, pas un théorème de mathématiques;
• rien sur l'esprit humain. Que la pensée soit ou non un calcul au sens de Turing est une question de philosophie et de sciences cognitives; la thèse ne la tranche pas, et l'on trouve des chercheurs sérieux des deux côtés;
• rien sur ce qui est «facile à programmer». Tous les langages de programmation usuels sont équivalents en puissance de calcul; cela ne les rend pas également commodes.

Pourquoi ce n'est pas un théorème

C'est le point que l'on comprend mal le plus souvent. La thèse met en relation deux choses de natures différentes:

• à droite, «calculable par une machine de Turing»: un énoncé mathématique parfaitement défini;
• à gauche, «calculable par un procédé effectif»: une notion intuitive, qui n'a pas de définition mathématique.

Une démonstration a besoin de définitions des deux côtés. Tant que le membre de gauche reste informel, aucune démonstration n'est possible — c'est une affaire de logique, pas de difficulté. Et si l'on donnait une définition formelle au membre de gauche, la thèse deviendrait démontrable ou réfutable, mais on aurait simplement déplacé la question: pourquoi cette définition-là serait-elle la bonne formalisation de l'intuition?

Ce qui soutient la thèse, ce sont donc des arguments, tous solides, aucun décisif:

1. La convergence des modèles. Le $\lambda$-calcul, les fonctions récursives générales, les machines de Turing, les machines à registres, les systèmes de réécriture, les automates cellulaires et tous les langages de programmation usuels définissent la même classe de fonctions. Ces modèles ont été conçus indépendamment, à partir d'intuitions différentes, et ils tombent tous au même endroit. C'est le genre de coïncidence qui suggère qu'il y a là un objet naturel.
2. L'analyse de Turing. Son article ne postule pas le modèle: il analyse ce que fait une personne qui calcule, et argumente que la finitude de la mémoire immédiate et la finitude du nombre de symboles distinguables imposent la forme du modèle. C'est une analyse conceptuelle, pas une démonstration, mais elle est remarquablement convaincante.
3. Quatre-vingt-dix ans sans contre-exemple. Personne n'a jamais proposé un procédé que l'on accepterait de qualifier de mécanique et qui sortirait de la classe.

Le problème de l'arrêt

L'énoncé

Voici un outil que tout programmeur voudrait posséder. On aimerait un analyseur qui, recevant le code d'un programme et son entrée, réponde: «ce programme finira» ou «ce programme bouclera indéfiniment». Il éviterait les serveurs figés, les boucles infinies en production, les tests qui ne rendent jamais la main.

Notons d'abord ce qui est possible. On peut parfaitement écrire un programme qui simule $P$ sur $w$: la machine universelle fait exactement cela. Si $P$ s'arrête, la simulation s'arrête et l'on répond «oui». Le problème est le cas contraire: si $P$ ne s'arrête pas, la simulation ne s'arrête pas non plus, et l'on n'obtient jamais de réponse. On dit que $\text{ARREˆT}$ est semi-décidable: on sait reconnaître les «oui», on ne sait pas reconnaître les «non». Le théorème dit que c'est le mieux que l'on puisse faire.

Démonstration. Raisonnons par l'absurde et supposons qu'un tel programme $H$ existe. Ses propriétés supposées sont, précisément:

et $H$ s'arrête toujours, sur toute entrée. C'est ce dernier point qui est fort: $H$ ne simule pas, il décide.

Construction du programme diagonal. Puisque $H$ existe, nous pouvons l'utiliser comme sous-programme. Définissons le programme $D$, qui prend en entrée un mot $x$:

programme D(x):
    reponse ← H(x, x)          # x est utilisé à la fois comme programme et comme entrée
    si reponse = "oui":
        tant que vrai: ne rien faire      # D boucle indéfiniment
    sinon:
        retourner                          # D s'arrête

Trois vérifications sur cette construction, car tout se joue là:

1. $D$ est un programme parfaitement légitime. Il ne fait qu'appeler $H$, tester une valeur booléenne et exécuter soit une boucle infinie, soit rien. Si $H$ existe, $D$ existe.
2. $D$ s'arrête toujours ou boucle toujours de façon bien définie: comme $H$ s'arrête sur toute entrée, l'appel $H(x,x)$ rend toujours la main, et $D$ entre alors soit dans la boucle, soit dans le retour. Il n'y a pas de troisième issue.
3. L'entrée $x$ est utilisée deux fois, comme et comme . C'est licite, puisque est un mot comme un autre: c'est la leçon de la machine universelle.

Par construction, pour tout mot $x$:

Le coup de la diagonale. $D$ est un programme; il a donc une description $⟨D⟩$. Rien ne nous interdit de lui donner cette description en entrée. Appliquons (5.2) avec $x=⟨D⟩$:

Posons $A$ l'affirmation «$D$ s'arrête sur $⟨D⟩$». La relation (5.3) dit $A⟺\neg A$. Si $A$ est vraie, elle est fausse; si elle est fausse, elle est vraie. C'est une contradiction dans les deux cas.

Aucune des étapes de la construction de $D$ n'est douteuse: appeler un sous-programme, tester, boucler, passer un mot en argument. La seule hypothèse dont nous puissions nous défaire est celle de départ. Donc $H$ n'existe pas. $\square$

Pourquoi «diagonalisation»

La figure 5.2 explique le nom. Rangeons tous les programmes en une liste $P_1,P_2,P_3,\dots$ — c'est possible, car un programme est un mot fini sur un alphabet fini, et l'on peut énumérer les mots par longueur croissante puis par ordre alphabétique. Construisons la table dont la case $(i,j)$ dit si $P_i$ s'arrête sur . Le programme est défini par : en colonne , il fait le contraire de ce que fait sur sa propre description. Par construction, diffère de en colonne , de en colonne , et ainsi de suite: il diffère de ligne. Il n'est donc aucun des — alors qu'il devrait y figurer, puisque c'est un programme et que la liste les contient tous.

C'est très exactement l'argument par lequel Cantor démontre que $\mathbb{R}$ n'est pas dénombrable, transporté des nombres réels aux programmes. Et l'analogie va plus loin: elle donne, gratuitement, un second théorème d'incalculabilité, non constructif celui-là.

Démonstration. Un programme est un mot fini sur un alphabet fini; l'ensemble de ces mots est dénombrable (énumérer par longueur croissante, puis par ordre alphabétique à longueur fixée). Chaque programme calcule au plus une fonction $\mathbb{N}\to \{0,1\}$, donc l'ensemble des fonctions calculables est dénombrable. Or l'ensemble de toutes les fonctions $\mathbb{N}\to \{0,1\}$ est en bijection avec l'ensemble des parties de $\mathbb{N}$, qui n'est pas dénombrable (argument diagonal de Cantor). Un ensemble non dénombrable ne peut pas être contenu dans un ensemble dénombrable: il existe des fonctions non calculables. $\square$

Ce théorème est plus fort en quantité et plus faible en contenu que le théorème 5.3: il dit qu'il y en a énormément, mais il n'en exhibe aucune. Le problème de l'arrêt, lui, en exhibe une, et ce n'est pas une fonction exotique: c'est la question qu'un développeur se pose toutes les semaines.

Ce que le théorème dit — et ce qu'il ne dit pas

Cette section vaut la démonstration elle-même, car ce résultat est l'un des plus mal cités de toute l'informatique.

Il dit: impossible, pas difficile. Ce n'est pas une question de puissance de calcul, de mémoire ou de patience. Un ordinateur mille milliards de fois plus rapide, avec une mémoire de la taille de l'univers, ne déciderait pas davantage l'arrêt. Le résultat est de même nature que «il n'existe pas de rationnel dont le carré vaut $2$»: ce n'est pas qu'on ne l'a pas trouvé.

Il ne dit pas qu'on ne peut rien dire d'un programme. C'est la mauvaise lecture la plus fréquente. Le théorème porte sur une procédure universelle et exacte: une qui réponde correctement pour tous les programmes et toutes les entrées. Renoncer à l'un de ces trois adjectifs rend la tâche possible:

• Renoncer à l'universalité. Pour une classe restreinte de programmes, l'arrêt est parfaitement décidable. Un programme sans boucle ni récursion s'arrête toujours. Une boucle pour i de 1 à n s'arrête toujours. Tout un langage de programmation peut être conçu pour que tous ses programmes terminent (c'est le cas des langages d'assistants de preuve, où la terminaison est vérifiée par le typage); on y perd la capacité d'exprimer toutes les fonctions calculables, ce qui est un prix qu'on paie sciemment.
• Renoncer à l'exactitude d'un côté. Un analyseur peut répondre «s'arrête», «ne s'arrête pas», ou «je ne sais pas». Rien dans le théorème n'interdit un tel outil; il interdit seulement qu'il n'ait jamais à dire «je ne sais pas». C'est exactement ce que font les analyseurs statiques industriels, les détecteurs de boucles infinies des compilateurs et les vérificateurs de terminaison.
• Renoncer à la totalité. On peut simuler le programme pendant dix secondes et répondre selon ce qu'on observe. C'est une heuristique, pas une décision.

Il ne dit pas que la contradiction vient de l'auto-référence «interdite». Rien n'est interdit: c'est parce que l'auto-application est parfaitement licite — un programme est une donnée — que l'hypothèse doit tomber.

Autres problèmes indécidables: la méthode des réductions

Démontrer l'indécidabilité à partir de zéro, par diagonalisation, est laborieux. On procède presque toujours autrement: en réduisant le problème de l'arrêt au problème étudié.

Démonstration. Supposons $B$ décidable par un algorithme $\mathcal{B}$, et soit $f$ la réduction. L'algorithme suivant décide $A$: sur l'entrée $x$, calculer $f(x)$ — cela s'arrête, par définition d'une réduction — puis exécuter $\mathcal{B}$ sur $f(x)$ et rendre sa réponse. Il s'arrête toujours, comme composition de deux procédures qui s'arrêtent, et il est correct par l'équivalence (5.4). $\square$

Un exemple complet: «ce programme imprime-t-il bonjour?»

Démonstration. Réduisons $\text{ARREˆT}$ à ce problème, que nous appelons $\text{BONJOUR}$. À partir d'une instance $(⟨P⟩,w)$ de l'arrêt, construisons le programme $P^{\prime }$ suivant:

programme P'():
    # 1. retirer du code de P toute instruction d'affichage
    #    (les remplacer par des instructions sans effet)
    executer P_muet sur l'entree w
    afficher "bonjour"

La transformation $(⟨P⟩,w)\mapsto ⟨P^{\prime }⟩$ est purement syntaxique: on parcourt le texte de $P$, on neutralise ses affichages, on enrobe le tout. Elle s'arrête toujours — c'est un traitement de texte, il ne dépend pas de ce que $P$ fait. C'est bien une réduction au sens de la définition.

Vérifions l'équivalence (5.4). Si $P$ s'arrête sur $w$, alors $P^{\prime }$ atteint sa dernière ligne et affiche bonjour: c'est une instance «oui» de $\text{BONJOUR}$. Si $P$ ne s'arrête pas sur $w$, alors $P^{\prime }$ reste indéfiniment dans la simulation et n'affiche jamais rien — en particulier jamais bonjour, puisque les affichages de $P$ ont été neutralisés. C'est une instance «non». Donc

c'est-à-dire $\text{ARREˆT}\le \text{BONJOUR}$. Comme $\text{ARREˆT}$ est indécidable (théorème 5.3), le théorème 5.5 donne le résultat. $\square$

Remarquez l'importance de la neutralisation des affichages: sans elle, un $P$ qui écrirait bonjour de lui-même avant de boucler ferait basculer l'équivalence. Une réduction est une construction précise, pas une analogie.

D'autres indécidables, et un théorème qui les balaie tous

La même technique donne, sans idée nouvelle:

• l'équivalence de deux programmes: «$P_1$ et $P_2$ rendent-ils la même sortie sur toute entrée?» est indécidable. Un compilateur ne peut donc pas décider en général si son optimisation a préservé la sémantique — il applique des transformations dont la correction est prouvée individuellement;
• la totalité: «$P$ s'arrête-t-il sur toutes les entrées?»;
• l'atteignabilité d'une ligne: «l'instruction de la ligne 42 est-elle exécutée un jour?», donc aussi «ce code est-il mort?», «cette division par zéro peut-elle se produire?», «cette variable peut-elle être nulle ici?»;
• la question de savoir si un programme calcule la fonction constante nulle, si son langage est vide, s'il est fini, s'il est régulier;
• le problème de correspondance de Post, purement combinatoire (assembler des dominos portant deux mots pour que la ligne du haut et celle du bas coïncident): aucun programme ne le décide;
• le dixième problème de Hilbert: décider si une équation polynomiale à coefficients entiers admet une solution en nombres entiers. Il a fallu soixante-dix ans de travaux, achevés par Matiyasevich en 1970, pour montrer qu'il est indécidable. C'est un énoncé d'arithmétique pure, sans un mot d'informatique: l'indécidabilité n'est pas un accident du vocabulaire des programmes.

Ce foisonnement n'est pas un hasard. Il est expliqué par un théorème que nous énonçons informellement, sa démonstration relevant d'un cours de calculabilité.

Autrement dit: toute question sémantique non triviale sur les programmes est indécidable. «Ce programme calcule-t-il le tri?», «rend-il toujours un nombre pair?», «boucle-t-il sur au moins une entrée?» — toutes indécidables, immédiatement, sans réduction à écrire.

L'hypothèse «porte sur ce que le programme calcule, et non sur la manière dont il est écrit» est essentielle et c'est elle qui sauve l'analyse de programmes. Les propriétés syntaxiques échappent au théorème et sont parfaitement décidables: «ce programme comporte-t-il plus de 100 lignes?», «contient-il une instruction goto?», «tous ses noms de variables sont-ils déclarés?», «ce code compile-t-il?». C'est sur ces propriétés-là, et sur des approximations prudentes des propriétés sémantiques, que travaillent les vérificateurs de types, les analyseurs statiques et les outils de style.

Ce qui est calculable mais coûteux: les classes P et NP

Passons la frontière. Tous les problèmes qui suivent sont décidables: pour chacun, un algorithme existe, et l'on peut même l'écrire en trois lignes — essayer toutes les possibilités. La question devient: en combien de temps?

La classe P

Cette définition demande deux justifications, et il faut donner les deux, y compris ses faiblesses.

Pourquoi «polynomial»? D'abord parce que la classe est robuste: elle ne dépend pas du modèle de machine. Passer d'une machine à $k$ rubans à une machine à un ruban, d'une machine de Turing à une machine à registres, d'un langage à un autre, multiplie le temps par un polynôme; et un polynôme d'un polynôme est un polynôme. $\mathsf{P}$ est donc une propriété du problème, pas de la machine ni du langage — ce qui n'est vrai d'aucune définition plus fine («temps linéaire» dépend du modèle). Ensuite parce que la classe est stable par composition: un algorithme polynomial qui appelle un nombre polynomial de fois un sous-programme polynomial reste polynomial. C'est ce qui permet de raisonner.

Pourquoi c'est une idéalisation. Un algorithme en $\Theta (n^{100})$ est dans $\mathsf{P}$ et parfaitement inutilisable; un algorithme en $\Theta (2^{n/1000})$ n'y est pas et serait excellent jusqu'à $n=50000$. De plus, «polynomial» ne dit rien des constantes, comme le chapitre 2 l'a souligné pour $O(\cdot )$. Et même honnêtement polynomial ne veut pas dire rapide: un algorithme cubique sur $n=10^6$ données demande opérations, soit environ secondes — plus de trente ans — à un milliard d'opérations par seconde. L'identification de à «traitable en pratique» est une convention utile, pas un fait; on l'appelle parfois thèse de Cobham–Edmonds, et c'est bien une thèse.

Exemples de problèmes de $\mathsf{P}$, tous rencontrés dans les chapitres précédents ou immédiats: rechercher un élément dans un tableau trié ($\Theta ({\log }_{2}n)$, chapitre 3); trier ($\Theta (n{\log }_{2}n)$, chapitre 3); décider si un graphe est connexe par un parcours ($\Theta (n+m)$, chapitre 4), ou trouver un plus court chemin pondéré par l'algorithme de Dijkstra ( avec un tableau, avec un tas binaire, chapitre 4); calculer le PGCD de deux entiers par l'algorithme d'Euclide (polynomial en le nombre de chiffres); décider si un graphe est bipartite, c'est-à-dire 2-coloriable (un simple parcours en largeur suffit); décider si un entier est premier — un algorithme déterministe polynomial en le nombre de chiffres a été publié en 2002 par Agrawal, Kayal et Saxena, résolvant une question restée longtemps ouverte.

La classe NP: la vérification plutôt que la recherche

Considérons le problème suivant. Un graphe $G$ à $n$ sommets étant donné, existe-t-il une clique de taille $k$, c'est-à-dire $k$ sommets tous reliés deux à deux? L'algorithme évident énumère les $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ sous-ensembles de taille $k$: ce n'est pas polynomial. Mais si quelqu'un vous désigne $k$ sommets en affirmant qu'ils forment une clique, vous vérifiez en regardant paires. C'est immédiat.

Cette asymétrie entre trouver et vérifier est le cœur du sujet.

En une phrase: $\mathsf{NP}$ est la classe des problèmes dont les réponses «oui» admettent une preuve courte et facile à vérifier. La difficulté est de trouver le certificat; la vérification, elle, est bon marché.

Le nom trompe et il faut le dire tout de suite: $\mathsf{NP}$ signifie «non déterministe polynomial», pas «non polynomial». La définition historique passe par les machines de Turing non déterministes, celles dont la table de transition autorise plusieurs successeurs pour un même couple (état, symbole) et qui acceptent s'il existe au moins un chemin de calcul acceptant. Les deux définitions coïncident: le certificat est la suite des choix faits par la machine non déterministe le long d'un chemin acceptant, et réciproquement une machine non déterministe «devine» le certificat puis le vérifie. Nous gardons la définition par certificats, qui ne suppose aucun modèle exotique.

Quelques exemples, avec leur certificat:

Deux inclusions élémentaires, à savoir démontrer.

Démonstration. Soit $L\in \mathsf{P}$, décidé par un algorithme $\mathcal{A}$ polynomial. Prenons pour vérificateur $V(x,c)=\mathcal{A}(x)$, qui ignore purement et simplement le certificat, et pour certificat le mot vide. Si $x\in L$, alors $V(x,\epsilon )$ répond «oui»; si $x\notin L$, alors répond «non» quel que soit , puisqu'il ne le lit pas. est polynomial. Donc .

Autrement dit, quand on sait résoudre soi-même, on n'a besoin d'aucune aide. Notons aussi que tout problème de $\mathsf{NP}$ est décidable en temps exponentiel: il suffit d'énumérer tous les certificats possibles, qui sont au plus $2^{n^k}$ (en binaire), et de lancer $V$ sur chacun. $\mathsf{NP}$ ne contient donc aucun problème indécidable; le problème de l'arrêt n'y est pas, et il n'y sera jamais.

Réduction polynomiale, NP-difficile, NP-complet

Nous avons utilisé les réductions pour transporter l'indécidabilité. Le même geste, avec une contrainte de coût, transporte la difficulté.

Démonstration. Soit $f$ la réduction, calculable en temps $O(n^a)$, et $\mathcal{B}$ un algorithme décidant $B$ en temps $O(m^b)$ sur une entrée de taille $m$. Sur une entrée $x$ de taille $n$, l'algorithme «calculer , puis exécuter sur » est correct par définition de la réduction. Pour le coût: un algorithme en ne peut plus de symboles, donc ; l'exécution de coûte donc , et le total est polynomial. La transitivité s'obtient de même, en composant les deux transformations.

L'argument sur la taille de $f(x)$ mérite qu'on s'y arrête: c'est lui qui fait fonctionner toute la théorie. Une réduction polynomiale ne peut pas faire exploser la taille de l'instance, pour la simple raison qu'elle n'a pas le temps de l'écrire.

Un problème $\mathsf{NP}$-complet est donc un problème le plus difficile possible dans $\mathsf{NP}$: tous les autres s'y ramènent. Deux conséquences se lisent aussitôt sur la définition.

Démonstration. Soit $B$ un problème $\mathsf{NP}$-complet appartenant à $\mathsf{P}$. Pour tout $A\in \mathsf{NP}$, on a $A{\le }_{p}B$ par $\mathsf{NP}$-difficulté, donc $A\in \mathsf{P}$ par le théorème 5.9. Ainsi , et l'inclusion inverse est le théorème 5.8: . Pour la réciproque, soit et un problème -complet: si était dans , la première partie donnerait , contredisant l'existence de .

C'est un énoncé remarquable, et c'est lui qui donne son intérêt à la notion: des milliers de problèmes issus de domaines sans rapport — logique, graphes, ordonnancement, planification, biologie computationnelle, jeux — sont $\mathsf{NP}$-complets, et ils tombent ou résistent ensemble. Un algorithme polynomial pour l'un d'eux les résoudrait tous.

Le point de départ: SAT et le théorème de Cook–Levin

La définition de la $\mathsf{NP}$-difficulté quantifie sur tous les problèmes de $\mathsf{NP}$: comment établir un premier exemple? C'est le tour de force de Cook, en 1971, et indépendamment de Levin en Union soviétique au début des années 1970.

Nous l'admettons, et voici la raison — car un «admis» sans raison n'a aucune valeur pédagogique. Que SAT soit dans $\mathsf{NP}$ est immédiat: l'affectation est le certificat, et l'évaluer est linéaire. La difficulté est l'autre moitié: montrer que tout problème de $\mathsf{NP}$ se réduit à SAT. La démonstration consiste à prendre un problème $A\in \mathsf{NP}$ quelconque, donc une machine de Turing non déterministe $M$ qui le décide en temps $n^k$, et à coder l'existence d'un calcul acceptant de $M$ sur $x$ par une formule booléenne. On introduit une variable pour chaque assertion élémentaire du type «à l'instant , la case du ruban contient le symbole », «à l'instant , la tête est en position », «à l'instant , l'état est »; puis on écrit des clauses exprimant que la configuration initiale est correcte, que chaque case ne contient qu'un symbole, que le passage de l'instant à l'instant respecte la table de transition, et qu'un état acceptant est atteint. La formule obtenue a une taille polynomiale en (il y a variables) et elle est satisfaisable si et seulement si accepte . C'est une construction longue et entièrement explicite, sans zone d'ombre, mais l'écrire en détail demanderait une dizaine de pages de vérifications mécaniques qui n'apprendraient rien de plus que ce paragraphe: c'est pourquoi nous l'admettons. Retenez l'idée: .

Une fois SAT établi, la machine se met en marche: pour montrer qu'un nouveau problème $B$ est $\mathsf{NP}$-difficile, il suffit de réduire un seul problème déjà connu $\mathsf{NP}$-difficile à $B$, la transitivité de ${\le }_p$ faisant le reste. En 1972, Karp publie vingt et un problèmes $\mathsf{NP}$-complets obtenus ainsi par une cascade de réductions à partir de SAT; la liste n'a cessé de s'allonger depuis.

Un catalogue à connaître

Tous les problèmes ci-dessous sont $\mathsf{NP}$-complets (dans leur version décision). Ils viennent de mondes différents, ce qui est le point.

• 3-SAT: satisfaire une formule dont chaque clause a trois littéraux. Par contraste, 2-SAT — deux littéraux par clause — est dans $\mathsf{P}$: on le résout par un parcours de graphe (chapitre 4) sur le graphe d'implications. La frontière entre facile et difficile passe entre 2 et 3.
• CLIQUE: existe-t-il $k$ sommets deux à deux adjacents?
• ENSEMBLE INDÉPENDANT (stable): existe-t-il $k$ sommets deux à deux non adjacents?
• COUVERTURE PAR SOMMETS: existe-t-il $k$ sommets touchant toutes les arêtes?
• COLORIAGE: peut-on colorier les sommets avec 3 couleurs sans que deux voisins partagent la même? Avec 2 couleurs, c'est dans $\mathsf{P}$ (bipartition). Même frontière qu'entre 2-SAT et 3-SAT.
• SAC À DOS: des objets ayant chacun un poids et une valeur, peut-on atteindre la valeur $V$ sans dépasser le poids $W$?
• VOYAGEUR DE COMMERCE (version décision): existe-t-il un circuit passant par toutes les villes, de longueur au plus $B$? La version optimisation («quel est le circuit le plus court?») n'est pas un problème de décision; elle est -difficile sans être dans , faute d'un certificat vérifiable en temps polynomial — car vérifier qu'un tour est demanderait de comparer à tous les autres.

P contre NP

Une question ouverte, et elle l'est vraiment

Nous savons $\mathsf{P}\subseteq \mathsf{NP}$. La question est de savoir si l'inclusion est stricte.

Ce que chaque réponse signifierait:

• Si $\mathsf{P}=\mathsf{NP}$: tout problème dont on peut vérifier rapidement une solution admet un algorithme rapide pour en trouver une. L'ordonnancement, la planification, le repliement de protéines, la conception de circuits, la recherche automatique de démonstrations mathématiques deviendraient — en principe — traitables. Et la cryptographie à clé publique telle que nous la connaissons s'effondrerait, puisque casser un chiffrement, c'est trouver une clé dont on vérifie aisément qu'elle est la bonne. Attention toutefois: cette conséquence n'est spectaculaire que si la démonstration est constructive et si les exposants et les constantes sont petits. Une preuve non constructive de $\mathsf{P}=\mathsf{NP}$, ou un algorithme en $n^{100}$, ne changerait rien à la pratique.
• Si $\mathsf{P}\ne \mathsf{NP}$: cela confirmerait l'intuition et justifierait a posteriori qu'on ait cessé de chercher des algorithmes exacts et rapides pour ces problèmes. Mais — et c'est un point trop rarement dit — cela à fonder la cryptographie, car est une affirmation sur le : elle dit qu'aucun algorithme polynomial ne réussit sur les instances, pas qu'un problème est difficile sur les instances qu'on rencontre, ni sur des instances tirées au hasard. La sécurité, elle, a besoin de difficulté .

Quelques précisions sur la figure 5.3. La classe $\mathsf{NP}$-difficile déborde largement de $\mathsf{NP}$: elle contient des problèmes bien plus durs, et même le problème de l'arrêt, qui est $\mathsf{NP}$-difficile (tout problème de $\mathsf{NP}$ s'y réduit) tout en étant indécidable. Être $\mathsf{NP}$-difficile n'implique donc pas d'être dans $\mathsf{NP}$: c'est pourquoi $\mathsf{NP}$-complet, qui exige les deux, est une notion strictement plus forte. La factorisation des entiers (dans sa version décision) est dans $\mathsf{NP}$, n'est pas connue pour être dans $\mathsf{P}$, et n'est pas connue pour être $\mathsf{NP}$-complète: elle occupe la zone intermédiaire, dont on ignore si elle est vide.

Ce qu'on fait vraiment des problèmes NP-complets

Un peu plus loin, et ce qu'on sait vraiment

Il serait malhonnête de laisser croire qu'on ne sait rien séparer. La chaîne d'inclusions

($\mathsf{PSPACE}$: mémoire polynomiale; $\mathsf{EXPTIME}$: temps $2^{n^k}$) est connue, et aucune de ces trois inclusions n'est connue pour être stricte. En revanche, le théorème de hiérarchie en temps établit que $\mathsf{P}\ne \mathsf{EXPTIME}$: donner strictement plus de temps permet strictement plus de choses. Cela suffit à conclure qu'au moins une des trois inclusions ci-dessus est stricte — sans qu'on sache laquelle. Voilà l'état exact du savoir: on sait qu'il y a une marche quelque part dans l'escalier, on ne sait pas sur quelle marche.

Signalons enfin un phénomène qui explique la difficulté de la question elle-même: plusieurs familles de techniques de démonstration ont été prouvées incapables de trancher $\mathsf{P}$ contre $\mathsf{NP}$ (les arguments dits de relativisation en sont le premier exemple). Ce n'est pas seulement qu'on n'a pas trouvé la preuve: on a démontré que certaines routes n'y mènent pas.

De la difficulté supposée à la sécurité: le pont vers le chapitre 9

Le chapitre 9 construira des systèmes cryptographiques. Il faut savoir dès maintenant sur quoi ils reposent, parce que c'est une conséquence directe de tout ce chapitre.

Le chiffrement à clé publique fonctionne ainsi: on choisit une opération facile à faire et — croit-on — difficile à défaire. Multiplier deux grands nombres premiers est facile; retrouver les facteurs d'un produit de 2048 bits, personne ne sait le faire en un temps raisonnable. Élever un nombre à une puissance modulo un premier est facile; retrouver l'exposant (le logarithme discret) est réputé difficile.

Trois remarques, et ce sont exactement les trois honnêtetés que ce chapitre a essayé d'installer.

1. Ces problèmes sont dans $\mathsf{NP}$ (leur version décision): un facteur, un exposant, se vérifient en une multiplication. La sécurité ne peut donc pas venir de l'indécidabilité: il n'y a aucun problème indécidable dans $\mathsf{NP}$, et de toute façon un système dont le déchiffrement légitime serait indécidable serait inutilisable.
2. Aucun de ces problèmes n'est connu comme $\mathsf{NP}$-complet, et l'on ne sait pas non plus qu'il n'est pas dans $\mathsf{P}$. La factorisation occupe la zone intermédiaire de la figure 5.3. Sa difficulté est une hypothèse, appuyée sur des décennies d'attaques infructueuses — le meilleur état de la connaissance publique, pas un théorème.
3. Même $\mathsf{P}\ne \mathsf{NP}$ ne suffirait pas, pour la raison déjà dite: la cryptographie a besoin d'instances difficiles en moyenne, pas seulement dans le pire cas. Et les modèles de calcul peuvent changer: un ordinateur quantique de taille suffisante casserait la factorisation et le logarithme discret par l'algorithme de Shor, sans rien changer à $\mathsf{P}$ contre ni à la thèse de Church–Turing originale. C'est ce qui motive les travaux actuels sur la cryptographie dite post-quantique.

La conclusion de ce chapitre tient donc en une phrase, et elle est inconfortable: la sécurité de la quasi-totalité des communications chiffrées repose aujourd'hui sur des problèmes que l'on croit difficiles, et «croit» est le mot exact. Ce n'est pas une faiblesse du raisonnement de ce cours; c'est l'état du savoir, et l'ingénierie s'en accommode en surdimensionnant les paramètres et en préparant des solutions de rechange.

Synthèse

• La question «tout problème admet-il un algorithme?» n'a de sens qu'une fois «algorithme» formalisé. La machine de Turing — ruban, tête, ensemble fini d'états, table de transition — est ce modèle; il est minuscule, il est lent, et il calcule tout ce que calcule n'importe quel langage de programmation. La machine universelle exécute n'importe quelle machine dont on lui donne la description: un programme est une donnée, et c'est aussi bien ce qui rend l'informatique possible que ce qui la limite.
• La thèse de Church–Turing identifie le calculable intuitif au calculable par machine de Turing. Ce n'est pas un théorème, et ce ne peut pas en être un: l'un de ses deux membres est informel. Elle est soutenue par la convergence de modèles indépendants et par quatre-vingt-dix ans sans contre-exemple. Elle ne dit rien de l'efficacité, ni de la physique, ni de la cognition.
• Le problème de l'arrêt est indécidable (théorème 5.3): en supposant un décideur $H$, on construit $D$ qui fait le contraire de ce que $H$ prédit de $D$ lui-même, et $D$ appliqué à sa propre description contredit les deux cas. «Indécidable» veut dire impossible, pas difficile — et cela n'interdit ni les analyseurs statiques, ni les langages dont tous les programmes terminent, ni les outils qui ont le droit de répondre «je ne sais pas».
• Par réduction depuis l'arrêt, une foule de problèmes sont indécidables: équivalence de deux programmes, atteignabilité d'une ligne, affichage d'un mot donné, dixième problème de Hilbert. Le théorème de Rice en donne la raison générale: toute propriété non triviale de est indécidable. Les propriétés , elles, restent décidables, et c'est là que vit l'analyse de programmes.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Sipser, M., Introduction to the Theory of Computation, Cengage, Boston — chapitres 3 à 7: le texte de référence pour les machines de Turing, l'indécidabilité et la NP-complétude.
• Turing, A. M., On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 1936 — l'article fondateur; sa section d'analyse du calcul humain se lit encore aujourd'hui.
• Cook, S. A., The Complexity of Theorem-Proving Procedures, Proceedings of the 3rd ACM Symposium on Theory of Computing, 1971 — le théorème de NP-complétude de SAT.
• Karp, R. M., Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press, 1972 — les vingt et un problèmes NP-complets.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, MIT Press — chapitre sur la NP-complétude, orienté algorithmique.
• Garey, M. R. et Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman — le catalogue historique des problèmes NP-complets.