Voir au préalable La machine de Turing (1/2)

La complexité algorithmique a pour objectif de mesurer la quantité de ressources (en temps ou en espace mémoire) pour réaliser quelque chose avec un dispositif particulier (par exemple une machine de Turing). Là où la calculabilité détermine si on peut le faire en théorie, la complexité précise ce que l’on va consommer (en temps ou en espace mémoire), au minimum [1], pour le faire. Autrement dit si on peut le faire en pratique [2].
On pourrait penser a priori que cela dépend du dispositif (de la machine) utilisé. C’est bien entendu exact d’un certain point de vue.
Mais on va voir que l’on peut définir une notion de complexité (asymptotique) qui ne dépend pas de la machine [3] utilisée.
La plupart des questions qui se posent alors pour cette complexité (comme le fameux problème « P est-il égal à NP ? ») ne sont pas résolues. Et elles sont fondamentales.

I. Bases

On va commencer par s’intéresser à la complexité en temps. Le coût $cost_M(w)$ en temps d’une machine de Turing déterministe appliquée à une entrée donnée w est égal au nombre de changements d’états que fait la machine pour arriver à un état final. On se limite à des entrées w pour lesquelles ce nombre de changements d’états est fini.

Dans ce contexte, il est judicieux de « se limiter » à un type particulier de machines de Turing. Ces machines de Turing ont deux états finaux : un état d’acceptation et un état de refus. Pour une entrée donnée, la « question » n’est plus de savoir ce que produit la machine, mais si l’on termine dans l’un ou l’autre état (si l’entrée est acceptée ou rejetée). [4] Si cette machine de Turing s’arrête pour toutes les entrées, on dit qu’elle « décide » (sous-entendu toujours si l’entrée est acceptée ou refusée). Comme on le verra plus loin, la « complexité d’un problème de décision » est la complexité d’une machine de Turing qui le résout (dans un sens que l’on précisera ; ce n’est pas une valeur numérique, c’est plutôt un O (grand O) d’une fonction)).
Comme on l’a vu dans l’article 1, le problème de l’arrêt (d’une machine de Turing, mais également d’un ordinateur) est indécidable, de même que celui de la vérité d’une assertion mathématique pour l’arithmétique (par exemple l’arithmétique de Peano ou toute théorie plus forte). On peut dire que la complexité de ces problèmes est infinie.
Un problème de calcul (une machine de Turing qui « calcule ») peut être ramené à un problème de décision dont la complexité est « sensiblement » la même. C’est ce que l’on fait en théorie. Le calcul de la fonction f(n) peut être transformé en le problème de décision « f(n) < k ? » ou en celui « le i-ème bit de f(n) est-il égal à 1 ? ». Si on sait calculer, on sait répondre à la question. Si on sait répondre à la question, on sait calculer. Et, grosso modo, les deux problèmes (le calcul et la réponse à la question) demandent le même temps d’exécution.

La complexité d’une machine de Turing M pour une entrée de taille n fixé est traditionnellement définie comme le maximum des coûts sur toutes les entrées de taille n.
$C_M(n) =\max\limits_{|w|=n} cost_M(w)$
On peut aussi s’intéresser à la complexité moyenne sur toutes les entrées de taille n.

Reprenons les machines de Turing de l’article 1. [5] On peut ajouter un compteur qui compte le nombre de changements d’état. Prenons par exemple la machine de Turing qui réalise une soustraction en unaire :

Soustraction en unaire

Faire une soustraction en unaire avec x < y : deux nombres X et Y sont écrits en unaire et séparés par un blanc, X est inférieur à Y et la tête est sous le chiffre de gauche deX.
On pourra, successivement, remplacer un 1 de X par un 0 et supprimer un 1 de Y.

Le départ

Le résultat

On peut alors facilement ajouter au programme un compteur de complexité, et tester le résultat :

Pour 1 & 1 (calcul 1 - 1), on obtient une complexité égale à 6.
Pour 1 & 2 (calcul 2 - 1), on obtient une complexité égale à 6.
Pour 1 & 3 (3 - 1), on obtient une complexité égale à 6.
Pour 1 & 4 (4 - 1), on obtient une complexité égale à 6.
Pour 1 & 5 (5 - 1), on obtient une complexité égale à 6.
Pour 1 & 6 (6 - 1), on obtient une complexité égale à 6.

Pour 2 & 2 (2 - 2), on obtient une complexité égale à 15.
Pour 2 & 3 (3 - 2), on obtient une complexité égale à 15.
...

Pour 3 & 3 (3 - 3), on obtient une complexité égale à 28.
Pour 3 & 4 (4 - 3), on obtient une complexité égale à 28.
...

Clairement, la complexité ne dépend que du premier nombre entré. Et le maximum est obtenu pour p & p (quand n est impair, car on tient compte de l’espace entre les deux nombres codés en unaire à soustraire) et pour p & p+1 (quand n est pair).
On peut alors tracer la courbe de la complexité (qui est une fonction de n) :

On obtient cette courbe :

En raccourci : on « reconnaît » la fonction carré. Donc on a une complexité en $O(n^2)$.

On dit qu’une machine de Turing est polynomiale s’il existe un polynôme Q tel que pour tout n, on a : $C_M(n) \leqslant Q(n)$.
C’est par exemple le cas de la machine de Turing ci-dessus (appliquée aux entrées valides) avec un polynôme Q de degré 2.

On pourrait alors créer un problème de décision associé à ce calcul (et de complexité « similaire »), par exemple : « le i-ème bit de la réponse est-il égal à 1 ? ».
Ce problème de décision est dans la classe P.

II. La classe P

Par définition, on dit qu’un problème de décision est dans P s’il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l’entrée. On dit que le problème est décidé en temps polynomial.

Propriété fondamentale : La classe P est stable par changement de modèle de calcul. [6]

Autrement dit, la classe P pour les machines de Turing à un seul ruban sur un alphabet à deux symboles est la même que la classe P pour les machines de Turing à plusieurs rubans sur un alphabet à deux ou plusieurs symboles.
Mais c’est aussi la classe P pour un ordinateur programmé dans un langage de programmation quelconque (pour lequel le coût en temps de calcul est le nombre d’instructions élémentaires exécutées par le processeur pendant ce calcul) !

Le coût en temps de calcul correspond au temps de calcul réel que met la machine pour faire ce calcul. Ce temps réel dépend bien sûr de la machine utilisée (vitesse du processeur, temps d’accès à la mémoire, etc), et diminue rapidement avec les progrès de la technologie (alors que le coût en temps de calcul, lui, ne varie pas). Par ailleurs, on peut démontrer que quand on change de modèle, le coût en temps de calcul se transforme de manière polynomiale (en général quadratique [7]).
La classe P regroupe donc tous les problèmes de décision demandant le même temps de calcul à une constante multiplicative près (état de la technologie) et à application d’un polynôme près (changement de modèle). Ce temps est toujours polynomial par rapport à la taille de l’entrée.

La classe P est importante car elle contient les problèmes que l’on considère « faisables » en pratique, autrement dit faciles à résoudre (dans le sens où on peut le faire relativement rapidement). Si un problème (résoluble par une machine de Turing) n’est pas dans P, il est faisable en théorie, mais en pratique, dès que la taille de l’entrée est grande, il est hors de portée.

Kurt Gödel, dans une lettre (retrouvée récemment) qu’il envoya à John von Neumann en 1956 quelques mois avant que celui-ci ne meure, envisageait déjà le problème de faisabilité, et son importance capitale.
Il demandait à von Neumann si, selon lui, la démonstration de théorème pouvait être résolue en temps quadratique ou linéaire. Sachant que, si c’était le cas, la découverte de preuves mathématiques pourrait être automatisée ainsi : pour toute question ouverte Q, on rechercherait parmi toutes les démonstrations de longueur n, n entier fixé, dans un système donné d’écriture des démonstrations (par exemple dans celui de la théorie des ensembles) s’il y en a une amenant la réponse. S’il y en a une, on la trouverait rapidement et on aurait résolu le problème Q ; si l’on n’en trouve pas et que le n essayé est assez grand, alors « il n’y aura plus de raison sérieuse de rester préoccupé par le problème » écrit Gödel. [8]

On peut démontrer que certains problèmes ne sont pas dans P, par exemple le problème d’évaluation d’une position dans les versions généralisées du jeu d’échec ou du jeu de dames (ces jeux sont généralisés dans le sens où la taille du plateau est donnée en entrée du problème).
On peut alors se demander si le problème de démonstration de théorème est dans P.
Ce problème a ceci de particulier qu’il s’agit de trouver s’il existe une solution parmi les entrées possibles, le problème de vérification d’une solution étant dans P. La classe de ces problèmes est appelées NP (N pour non déterministe ; il s’agit d’une classe P, mais pour les machines de Turing non déterministes).

III. La classe NP

La classe NP est une extension de la classe P, obtenue en autorisant des choix non déterministes pendant l’exécution de l’algorithme.
En terme de machine de Turing, on autorise cette fois une ou plusieurs transitions à partir d’un état et d’un symbole lu sur la bande (autrement dit l’emploi d’une machine de Turing non déterministe).
Une machine non déterministe s’arrête sur une entrée w s’il existe un chemin, partant de w, qui conduise de l’état initial à un état terminal. Pour définir NP, on se restreint à ce cas (pour toutes les entrées w).
Une machine non déterministe accepte une entrée w s’il existe un chemin, partant de w, qui conduise de l’état initial à l’état d’acceptation. Sinon, la machine refuse l’entrée w.
Le coût $cost_M(w)$ en temps d’une machine de Turing non déterministe appliquée à une entrée donnée w est égal au coût du chemin minimal (en nombre de transitions) qui aboutit à l’état d’acceptation (si le mot est accepté) ou à l’état de refus (si le mot est refusé).

Comme pour les machines de Turing déterministes, la complexité d’une machine de Turing non déterministe M pour une entrée de taille n fixé est traditionnellement définie comme le maximum des coûts sur toutes les entrées de taille n.
$C_M(n) =\max\limits_{|w|=n} cost_M(w)$
On peut aussi s’intéresser à la complexité moyenne sur toutes les entrées de taille n.

On l’a esquissé dans le cas du problème de démonstration de théorème, la classe NP peut aussi être vue en terme de vérificateur polynomial et de certificat.
Prenons par exemple le problème de la somme des sous-ensembles : on suppose que l’on nous donne des nombres entiers, {−7, −3, −2, 5, 8}, et on souhaite savoir si la somme de certains d’entre eux est égale à 0 . Ici, la réponse est « oui », puisque les entiers {−3, −2, 5} correspondent à la somme (−3) + (−2) + 5 = 0. Déterminer si un tel sous-ensemble avec une somme nulle existe est appelé le problème de la somme des sous-ensembles.
Pour répondre à la question, on peut créer un algorithme qui trouve tous les sous-ensembles possibles et teste si leur somme est nulle. À mesure que le nombre d’entiers que l’on introduit dans l’algorithme augmente, le nombre de sous-ensembles et le temps de calcul augmentent de manière exponentielle.
Mais si on nous donne un sous-ensemble particulier, on peut vérifier efficacement (en temps polynomial) si la somme du sous-ensemble est nulle. Si la somme est nulle, ce sous-ensemble est une preuve ou un certificat car la réponse est « oui ». Un algorithme qui vérifie si un sous-ensemble donné a une somme nulle est un vérificateur . Clairement, la sommation des entiers d’un sous-ensemble peut se faire en temps polynomial. On peut alors en déduire (d’après une propriété que l’on énoncera plus bas) que le problème de la somme des sous-ensembles est dans NP.

Plus généralement, un certificat est une information que l’on ajoute à une donnée du problème, pour certifier que la réponse au problème pour cette donnée est « oui » ou « non ».
Un problème de décision est dans la classe NP s’il existe pour chaque donnée ayant une réponse positive un certificat polynomial, c’est-à-dire s’il existe pour chaque donnée pour laquelle la réponse est « oui », un certificat de longueur polynomiale en la taille de la donnée, tel que la vérification de la réponse (par une machine de Turing appelée un vérificateur) pour la donnée munie de son certificat se réalise en temps polynomial.

Formellement, une machine de Turing déterministe V avec un état d’acceptation et un état de rejet et qui s’arrête pour toutes les entrées
est un vérificateur pour le problème de décision A si et seulement si :

$A(u) \Leftrightarrow \exists \thinspace x \thinspace V(u,x)$ accepte

Un argument x qui satisfait « V (u, x) accepte » est appelé un certificat de u ; un vérificateur est dit polynomial si sa complexité est $O( n^k )$, où n désigne la taille du premier argument u. Cette convention garantit que la taille du certificat est elle-même bornée par une fonction polynomiale de n (sinon, V n’aurait même pas le temps de lire le certificat).

On peut prouver le résultat suivant :

La classe NP est formée des problèmes de décision qui possèdent un vérificateur polynomial.

Cette nouvelle définition de NP est celle qu’on utilise presque toujours en pratique. Elle illustre la nature des problèmes appartenant à cette classe, qu’on peut résumer par : on devine et on vérifie (en temps polynomial) ; on n’a pas à rechercher le certificat (ce qui demanderait a priori un temps de calcul exponentiel), il est « miraculeusement » deviné ; on a ensuite un algorithme polynomial pour vérifier le certificat.

La version « non » du problème de la somme des sous-ensembles peut être formulée ainsi : « étant donné un ensemble fini d’entiers, est-ce que chaque sous-ensemble non vide a une somme non nulle ? ». Un problème est dans NP s’il possède un vérificateur polynomial. Mais à l’aide de ce vérificateur, on ne peut pas (jusqu’à preuve du contraire) créer de vérificateur polynomial pour les réponses « non ».
La classe de problèmes avec de tels vérificateurs pour les réponses « non » est appelée co-NP.
Le « problème », c’est le quantificateur (s’il y a un vérificateur qui accepte, il y en a aussi un qui refuse les mêmes entrées). Avec le quantificateur $\forall$ plutôt que $\exists$, on obtient la classe co-NP.
C’est une question ouverte de savoir si tous les problèmes dans NP ont également des vérificateurs pour les réponses « non » et sont donc dans co-NP.

IV. La question à 1 million de dollars

Le problème « P est-il égal à NP ? » est un des sept problèmes du prix du millénaire posés par l’institut Clay en 2000. Sa résolution est dotée d’un prix d’un million de dollars américains.

L’importance de ce problème est renforcée par l’existence (voire le foisonnement) de problèmes NP-complets.
Un problème NP-complet (c’est-à-dire un problème complet pour la classe NP) est un problème de NP tel que tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale.
Cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de NP.

Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d’exécution exponentiel en la taille des données d’entrée dans le pire des cas, et sont donc inexploitables en pratique.

Cette définition implique que s’il existe un algorithme polynomial pour résoudre un quelconque des problèmes NP-complets, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu’il n’en existe pas permettrait de savoir si P = NP ou P ≠ NP.

Le concept de NP-complétude a été introduit en 1971 par Stephen Cook dans une communication intitulée The complexity of theorem-proving procedures (La complexité des procédures de démonstration de problèmes). Le résultat de l’article de Cook, démontré de manière indépendante par Leonid Levin en URSS, est connu sous le nom de théorème de Cook-Levin. Ce théorème affirme qu’il existe un problème NP-complet.
Cook l’a démontré pour le problème SAT (satisfaisabilité d’une formule booléenne : étant donnée une formule de logique propositionnelle quelconque, existe-t-il une assignation des variables propositionnelles qui rend la formule vraie ?).

On laisse à l’appréciation du lecteur cet essai de vulgarisation, assez vertigineux -mais drôle-, de Scott Aronson (MIT) au sujet de la question « P est-il égal à NP ? » :
« Si P = NP, alors le monde serait un endroit profondément différent de ce qu’on imagine habituellement. Il n’y aurait aucune valeur spécifique au « saut créatif », aucun fossé séparant le fait de résoudre un problème et celui de reconnaître la validité d’une solution trouvée. Tous ceux capables d’apprécier une symphonie seraient Mozart ; tous ceux capables de suivre un raisonnement étape par étape seraient Gauss. Tous ceux capables de reconnaître une bonne stratégie d’investissement seraient Warren Buffet. »

V. Complexité spatiale

Un petit mot sur la complexité spatiale :
De la même façon qu’on définit la complexité temporelle d’un algorithme, on peut définir sa complexité spatiale pour évaluer sa consommation en espace mémoire. Pour une machine de Turing, on compte le nombre de cases visitées du(des) ruban(s) (sans tenir compte, s’ils existent, du ruban de lecture et du ruban d’écriture).
On peut alors définir PSPACE et NPSPACE.
D’après le e théorème de Savitch, on a : PSPACE=NPSPACE.
Et comme on a clairement NP $\subseteq$ NPSPACE, on a donc :

${{P}} \subseteq {{NP}} \subseteq {{PSPACE}} = {{NPSPACE}}$

On peut noter qu’actuellement le facteur limitant est plutôt la complexité temporelle que la complexité spatiale. En effet, on dispose souvent d’une grande quantité de mémoire vive.
Par conséquent, on porte généralement l’effort sur la complexité temporelle.