La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut être résolu par un ordinateur. La théorie de la complexité se concentre donc sur les problèmes qui peuvent effectivement être résolus, la question étant de savoir s'ils peuvent être résolus efficacement ou pas en se basant sur une estimation (théorique) des temps de calcul et des besoins en mémoire informatique.

Généralités

---

Machine déterministe et machine non déterministe

Une machine déterministe est le modèle formel d'une machine telle que nous les connaissons (nos ordinateurs sont des machines déterministes). Les deux modèles les plus utilisés en informatique théorique sont :

• La machine de Turing
• La machine RAM

Les machines déterministes font toujours un seul calcul à la fois, et donnent toujours le même résultat à condition que les données d'entrée soit identique (pour la génération de nombres aléatoires).

Les machines de Turing non-déterministes peuvent, elles, effectuer un nombre illimité d'opérations à la fois (c'est une vision purement théorique, car ces machines ne peuvent pas être construites -- la littérature parle parfois de machine à oracle). Il semblerait donc naturel de penser que les machines de Turing non-déterministes sont beaucoup plus puissantes que les machines de Turing déterministes, autrement dit qu'elles peuvent résoudre en un temps raisonnable des problèmes que les machines ordinaires ne savent pas résoudre à moins de prendre des années.

Les machines à ADN sont un cas particuliers de machines non-déterministes, puisqu'elles sont capable de traiter un calcul en temps constant quelque soit la taille des données. Notons toutefois que la difficulté est ici transposé en terme de réalisabilité de la machine, qui nécessite des quantités exponentielle d'ADN en fonction de la taille des données.

Complexité en temps et en mémoire

On désigne par n la taille de la donnée. On peut prendre quelques exemples :

• La donnée d'un graphe à s sommets et n arêtes est de taille $s^2$ si on choisit une représentation matricielle (il y a $s^2$ cellules dans la matrice à stocker et chacune vaut 0 ou 1).
• la taille d'un vecteur d'élément à trier.

Pour les machines déterministes, on définit la classe TIME(t(n)) des problèmes qui peuvent être résolus en temps t(n). C'est-à-dire pour lesquels il existe au moins un algorithme sur machine déterministe résolvant le problème en temps t(n) (le temps étant le nombre de transitions sur machine de Turing ou le nombre d’opérations sur machine RAM).

• TIME(t(n)) = { L ; L peut être décidé en temps t(n) par une machine déterministe }

Pour les machines non déterministes, on définit la classe NTIME(t(n)) des problèmes qui peuvent être résolus en temps t(n).

• NTIME(t(n)) = { L | L peut être décidé en temps t(n) par une machine non-déterministe }

La complexité en mémoire évalue l'espace mémoire utilisé en fonction de la taille des données.

Le problème du codage

Le codage influence la complexité des problèmes. Il est bon de se rappeler que les données sur lesquels travaillent les algorithmes sont nécessairement codée en mémoire (on parle ici de la mémoire de l'ordinateur, mais aussi de la bande de la machine de Turing par exemple).

Si le codage d'une donnée est exponentiel par rapport à la taille de la donnée initial, l'ensemble des complexités des algorithmes seront sans doute majorée par la complexité du codage.

On ne s'intéressera ici qu'aux codages raisonnables.

Problème de décision

L'ensemble des problèmes informatiques peuvent se réduire à des problèmes de décision. La réponse à un problème de décision est Oui ou Non. Un problème dont la réponse n'est ni Oui ni Non peut-être très simplement transformé en un problème de décision. Le problème du voyageur de commerce, qui cherche, dans un graphe, à trouver la taille du cycle le plus court passant une fois par chaque sommet, peut s'énoncer en un problème de décision ainsi : Existe-t-il un cycle passant une et une seule fois par chaque sommet tel que la somme des coûts des arcs utilisés soit inférieure à $B$, avec que $B\; \backslash in\; \backslash mathbb\{N\}$.

Classes de complexité

---

La théorie de la complexité repose sur la définition de classes de complexité qui permettent de classer les problèmes en fonction de la complexité des algorithmes qui existent pour les résoudre.

Classe L

Un problème de décision qui peut être résolu par un algorithme déterministe en espace logarithmique par rapport à la taille de l'instance est dans L.

Classe NL

Cette classe correspond à la précédente mais pour un algorithme non-déterministe.

Classe P

Un problème de décision est dans P s'il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l'instance. On qualifie alors le problème de polynomial.

Prenons par exemple un algorithme de tri assez simple qui est le tri à bulles. Cet algorithme trie un tableau d'éléments. S'il y a n éléments dans le tableau, l'algorithme de tri à bulle fera, dans le pire des cas, n² opérations. On dit alors que l'algorithme a une complexité polynômiale car sa complexité peut-être exprimée par un polynôme. Dans ce cas-ci, l'algorithme est en temps quadratique. Le problème du tri est donc dans P. Les problèmes dans P correspondent en fait à tous les problèmes facilement résolubles.

Classe NP

Un problème NP est Non-déterministe Polynomiale (et non pas Non polynomial qui est une erreur très courante).

C'est la classe des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance.

De façon équivalente, c'est la classe des problèmes qui admette un algorithme dans P qui, étant donné une solution du problème NP (un certificat), sont capable de répondre Oui ou Non.

Intuitivement, les problèmes dans NP sont tous les problèmes qui peuvent être résolus en énumérant l'ensemble des solutions possibles et en les testant avec un algorithme polynomial.

Par exemple, la recherche de cycle hamiltonien dans un graphe peut se faire avec deux algorithmes :

• le premier génère l'ensemble des cycles (ce qui est exponentiel) ;
• le second teste les solutions (temps polynomial) ;

Classe Co-NP

Nom parfois donné pour l'équivalent de la classe NP avec la réponse non.

Classe PSPACE

les problèmes décidables par un algorithme déterministe en espace polynomial par rapport à la taille de son instance.

Classe NSPACE ou NPSPACE

les problèmes décidables par un algorithme non-déterministe en espace polynomial par rapport à la taille de son instance.

Classe EXPTIME

les problèmes décidables par un algorithme déterministe en temps exponentiel par rapport à la taille de son instance.

Propriétés

On a les inclusions:

• P $\backslash subset$ NP
• Co-NP $\backslash subset$ PSPACE = NPSPACE.

En effet, un problème polynomial peut se résoudre en générant une solution et en la testant avec un algorithme polynomial. Tout problème dansPest aussi dans NP.

La recherche travaille activement à déterminer si NP $\backslash subset$ P (concluant à P = NP) ou si, au contraire P $\backslash ne$ NP (voir Le problème ouvert P = NP)

Problème C-Complet

Soit C une classe de complexité (comme P, NP, etc.). On dit qu'un problème est C-complet si

• il est dans C
• il est C-difficile (on utilise parfois la traduction incorrecte C-dur)

Un problème est C-difficile si ce problème est au moins aussi dur que tous les problèmes dans C. Formellement on définit une notion de réduction : soient $\backslash Pi$ et $\backslash Pi\text{'}$ deux problèmes, une réduction de $\backslash Pi\text{'}$ à $\backslash Pi$ est un algorithme transformant toute instance de $\backslash Pi\text{'}$ en une instance de $\backslash Pi$. Ainsi, si l'on a un algorithme pour résoudre $\backslash Pi$, on sait aussi résoudre $\backslash Pi\text{'}$. $\backslash Pi$ est donc au moins aussi difficile à résoudre que $\backslash Pi\text{'}$.

$\backslash Pi$ est alors C-difficile si pour tout problème $\backslash Pi\text{'}$ de C, $\backslash Pi\text{'}$ se réduit à $\backslash Pi$. Quand on parle de problèmes NP-difficiles on s'autorise uniquement des réductions dans P, c'est-à-dire que l'algorithme qui calcule le passage d'une instance de $\backslash Pi\text{'}$ à une instance de $\backslash Pi$ est polynomial (voir Réduction polynomiale. Quand on parle de problèmes P-difficiles on s'autorise uniquement des réductions dans LOGSPACE.

Réduction de problèmes

---

Il est possible de classer de façon formelle chaque problème en obtenant une réduction d'un problème dont la complexité est connu à ce nouveau problème.

Transformation de problème

La réduction la plus simple (ce n'est d'ailleurs pas vraiment une réduction) consiste simplement à transformer le problème à classer en un problème déjà classé.

Par exemple, démontrons ici que le problème de la recherche de cycle hamiltonien dans un graphe orienté est NP-Complet.

• Le problème est dans NP (on peut trouver de façon évident un algorithme pour le résoudre avec une machine non-déterministe, par exemple en énonçant tous les cycles et en sélectionnant le plus court).
• Nous avons à notre disposition le problème de la recherche de cycle hamiltonien pour les graphe non-orienté. Un graphe non-orienté peut se transformer en un graphe orienté en « doublant » chaques arêtes pour obtenir, entre chaque noeuds voisins, des chemins dans les deux sens. Il est donc possible de ramener le problème connus, NP-Difficile, au problème que nous voulons classer. Le nouveau problème est donc NP-Difficile.

Le problème étant dans NP et NP-Difficile, il est NP-Complet.

Réduction polynomiale

Voir l'article complet réduction polynomiale.

Théorème de Cook

Les problèmes sont classés de façon incrémentale, la classe d'un nouveau problème étant déduite de la classe d'un ancien problème.

Il a toutefois nécessité un « premier » problème NP-Complet pour classer tous les autres, c'est le théorème de Cook (de Stephen Cook), qui classe le problème SAT comme NP-Complet.

Problème NP-Complet

---

Les problèmes complets les plus étudiés sont les problèmes NP-complets. La classe de complexité étant par définition réservée à des problèmes de décisions, on parlera de problème NP-difficile pour les problèmes d'optimisation sachant que - pour ces problèmes d'optimisation - on peut construire facilement un problème qui lui est associé et est dans NP et qui est donc NP-complet.

De manière intuitive, dire qu'un problème peut être décidé à l'aide d'un algorithme non-déterministe polynomial signifie qu'il est facile, pour une solution donnée, de vérifier en un temps polynomial si celle-ci répond au problème pour une instance donnée (à l'aide d'un certificat); mais que le nombre de solutions à tester pour résoudre le problème est exponentiel par rapport à la taille de l'instance.

Le non-déterminisme permet de masquer la taille exponentielle des solutions à tester tout en permettant à l'algorithme de rester polynomial.

Problème NP-Complets célèbres :

• Problème SAT et variante 3SAT (mais 2SAT est polynomial) ; notons qu'il existe des logiciels (dits SAT solvers) spécialisés dans la résolution performante de problèmes SAT ;
• Problème du voyageur de commerce
• Problème du cycle hamiltonien
• Problème de la clique maximum
• Problèmes de colorations de graphes
• Problème d'ensemble dominant dans un graphe
• Problème de couverture de sommets dans un graphe

Bien que moins étudiés, les problèmes complets pour les autres classes ne sont pas moins intéressants

• Le problème Reach (ou Accessibilité) qui consiste à savoir s’il existe un chemin entre deux sommets d'un graphe est NL-complet
• Le problème Circuit Value (et monotone Circuit Value : le même mais sans négation) sont des problèmes P-complets
• Le problème QBF (SAT avec des quantificateurs) est PSPACE-complet

Remarque : tous les problèmes de la classe L sont L-complets vu que la notion de réduction est trop vague. En effet la fonction qui doit transformer un instance d'un problème à l'autre doit se calculer en espace logarithmique.

Le problème ouvert $P=NP$

---

On a trivialement $P\; \backslash subset\; NP$ car un algorithme déterministe est un algorithme non déterministe particulier. En revanche la réciproque : $NP\; \backslash subset\; P$, que l'on résume généralement à $P\; =\; NP$ du fait de la trivialité de l'autre inclusion, est l'un des problèmes ouverts les plus fondamentaux et intéressants en informatique théorique. Cette question a été posée en 1970 pour la première fois et celui qui arrivera à décider siPetNPsont différents ou égaux recevra le prix Clay (plus de 1 000 000 $)

Le problème $P\; =\; NP$ revient à savoir si on peut résoudre un problème NP-Complet avec un algorithme polynomial. Les problèmes étant tous classés les uns à partir des autres (un problème est NP-Complet si l'on peut réduire un problème NP-Complet connu en ce problème), faire tomber un seul de ces problèmes dans la classe P fait tomber l'ensemble de la classe NP, ces problèmes étant massivement utilisé en raison de leur difficulté par l'industrie, notamment en cryptographie (voir Factorisation_en_nombres_premiers). Ceci fait qu'on conjecture cependant que les problèmes NP-complets ne sont pas solubles en un temps polynomial. À partir de là plusieurs approches sont tentées :

• des algorithmes d'approximation permettent de trouver des solutions approchées de l'optimum en un temps raisonnable pour un certain nombre de programmes. Dans le cas d'un problème d'optimisation on trouve généralement une réponse correcte sauf que l'on en sait pas si c'est la meilleure solution.
• des algorithmes stochastiques : en utilisant des nombres aléatoires on peut «forcer» l'algorithme à ne pas utiliser les cas les moins favorables. C'est ainsi que récemment un algorithme de test de primalité qui fonctionne en temps polynomial a été découvert.
• des heuristiques permettent d'obtenir des solutions généralement bonnes mais non exactes en un temps de calcul modéré;
• des algorithmes par séparation et évaluation permettent de trouver la ou les solutions exactes. Le temps de calcul n'est bien sûr pas borné polynomialement mais, pour certaines classes de problèmes, il peut rester modéré pour des instances relativement grandes.
• on peut restreindre la classe des problèmes d'entrée à une sous-classe suffisante, mais plus facile à résoudre.

Si ces approches échouent, le problème est non soluble en pratique dans l'état actuel des connaissances.

Pour le cas de L et NL on ne sait pas non plus si $L\; =\; NL$ mais cette question est moins primordiale car $L\; \backslash subset\; NL\; \backslash subset\; P\; \backslash subset\; NP$. Ce qui fait que les problèmes qui sont dans L et dans NL sont solubles efficacement.

Inversement on sait que $PSPACE\; =\; NPSPACE$, mais par contre $NP\; \backslash subset\; PSPACE$. Donc avant de résoudre $NP\; =\; PSPACE$ il faut résoudre $P\; =\; NP$.

Pour résumer on a $L\; \backslash subset\; NL\; \backslash subset\; P\; \backslash subset\; NP\; \backslash subset\; PSPACE\; =\; NPSPACE$, et de plus on sait que NL est strictement inclus dans PSPACE et donc il y en a au moins deux entre NL et PSPACE qui ne sont pas égaux.

Modèles de calcul

---

Ces théorèmes ont été établis grâce au modèle des machines de Turing. Mais d'autres modèles sont utilisés en complexité, dont :

• les fonctions récursives dues à Kleene
• les automates cellulaires
• les automates à pile
• les machines à registres (RAM)
• le lambda-calcul

On sait que tous ces modèles sont équivalents : tout ce qu'un modèle permet de calculer est calculable par un autre modèle. De plus, grâce aux machines universelles de Turing, on sait que tout ce qui est intuitivement calculable est modélisable dans ces systèmes. Les conséquences sont importantes et nombreuses. La première fait que cet article est lisible : on peut construire des ordinateurs. Ceci fait un lien avec la théorie de la calculabilité.

Voir aussi

---

• Réduction polynomiale

Bibliographie

---

• Michael R. Garey, David S. Johnson, Computers and Intractability : A guide to the theory of NP-completeness, W.H. Freeman & Company, 1979. ISBN 0716710455
• Pierre Wolper, Introduction à la calculabilité, Dunod, 2001. ISBN 2100048538
• Richard Lassaigne, Michel de Rougemont, Logique et Complexité, Hermes, 1996. ISBN 2866014960
• Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993. ISBN 0201530821

Liens externes

---

• Le Zoo de la complexité
• Un compendium des problèmes de la classe NP

Algorithmique | Théorie | Logique mathématique | informatique

Komplexitätstheorie | Computational complexity theory | ?????? | Z?oz˙onos´c´ obliczeniowa | Komplexitetsteori | نظرية التعقيد