Théorie de la complexité (informatique théorique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorie de la complexité.
Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe.

La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (temps, espace mémoire, etc.) qu'a besoin un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes, de les organiser par classes de complexité., d'étudier les relations entre les classes de complexité.

Problèmes algorithmiques[modifier | modifier le code]

Le problème de voyageur de commerce ː calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes).

Considérons l'exemple du problème du voyageur de commerce. La donnée du problème est un ensemble de villes et de distances séparant ces villes. L'objectif du problème est de trouver un plus court circuit qui passe une et une seule fois par toutes les villes. Il existe un problème de décision associé : étant donné un ensemble de villes, les distances entre villes et un entier k, déterminer s'il existe un circuit qui passe une et une seule fois par toutes les villes de longueur inférieure à k. Ainsi, on distingue deux types de problèmes :

  • les problèmes de décision : ils posent une question dont la réponse est oui ou non ; dans le cas du problème du voyageur de commerce : existe-il oui ou non un circuit de longueur inférieure à k ?
  • les problèmes d'existence ou de recherche d'une solution : ils comportent une question ou plutôt une injonction de la forme « trouver un élément tel que… » dont la réponse consiste à fournir un tel élément; dans le cas du problème du voyageur de commerce, exhiber un circuit de longueur inférieure à k.

La théorie de la complexité étudie principalement (mais pas uniquement) les problèmes de décision.

Quelques exemples de problèmes de décision[modifier | modifier le code]

Un exemple de problème de décision est :

« Étant donné un entier n, est-il premier ? »

Instances[modifier | modifier le code]

Dans le cadre de la théorie de la complexité, la donnée d'un problème s'appelle une instance. Une instance du problème du voyageur de commerce est la donnée de villes et de distances séparant les villes. Comme on mesure la complexité en fonction de la taille d'une instance, la représentation (le codage) d'une instance joue un rôle important. Par exemple, un entier comme 13 peut être représenté en unaire (IIIIIIIIIIIII) ou en binaire (1101). En unaire, la taille de l'instance 13 est 13 et en binaire, la taille de l'instance est 4 (car il y a 4 chiffres dans 1101).

De l'existence à la décision[modifier | modifier le code]

Question book-4.svg
Cette section ne cite pas suffisamment ses sources (septembre 2013)
Pour l'améliorer, ajoutez des références vérifiables [comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Un problème d'existence peut être transformé en un problème de décision équivalent. Par exemple, le problème du voyageur de commerce qui cherche, dans un graphe dont les arêtes sont étiquetées par des coûts, à trouver un cycle, de coût minimum, passant une fois par chaque sommet, peut s'énoncer en un problème de décision comme suit : Existe-t-il un cycle passant une fois par chaque sommet tel que tout autre cycle passant par tous les sommets ait un coût supérieur ? L'équivalence de ces deux problèmes suppose que la démonstration d'existence repose sur un argument constructif[1], c'est-à-dire, par exemple, dans le cas du voyageur de commerce, fournissant effectivement un cycle de coût minimum dans le cas où l'on a montré qu'un cycle de coût minimum existe. Le problème de l'existence d'un cycle de coût minimum est équivalent au problème du voyageur de commerce, au sens où si l'on sait résoudre efficacement l'un, on sait aussi résoudre efficacement l'autre. Dans la suite de cet article, nous ne parlerons donc que de problèmes de décision.

Représentation d'un problème de décision[modifier | modifier le code]

Un problème de décision peut être vu comme l'ensemble des instances positives, c'est-à-dire les instances pour lesquelles la réponse est "oui". Par exemple, pour le problème de primalité, le problème de décision est l'ensemble des nombres premiers. Étant donné un codage des instances par des mots, on peut voir un problème de décision comme un langage formel : l'ensemble des mots qui représentent les instances positives.

Réponse algorithmique[modifier | modifier le code]

Considérons à présent un algorithme qui résout le problème du voyageur de commerce. L'algorithme exécute des étapes élémentaires de calcul et le nombre d'étapes dépend de la taille de l'entrée. Pour le problème du voyageur de commerce, la taille de l'entrée est la quantité de mémoire nécessaire pour représenter les villes et les distances qui les séparent. Pour mesurer le temps d'exécution d'un algorithme, on définit la complexité en temps qui représente le nombre d'étapes qui sont nécessaires pour résoudre le problème pour une entrée de taille donnée.

Bien sûr, il existe de nombreux algorithmes qui résolvent le même problème. La théorie de la complexité s'attache à connaître la difficulté (ou la complexité) intrinsèque d'un problème algorithmique. On classifie les problèmes (et non pas les algorithmes) en termes de classes de complexité.

Dans chaque catégorie de problèmes ci-dessus, on dit qu'un problème a une réponse algorithmique si sa réponse peut être fournie par un algorithme. Un problème de décision – donc un problème dont la réponse est soit oui soit non – est décidable si sa réponse peut être fournie par un algorithme. De la même façon, on dit qu'un problème d'existence est calculable si l'élément solution peut être calculé par un algorithme. La théorie de la complexité ne couvre que les problèmes décidables ou calculables et cherche à évaluer les ressources – temps et espace mémoire – mobilisées pour obtenir algorithmiquement la réponse.

Complexité d'un problème algorithmique[modifier | modifier le code]

La théorie de la complexité vise à savoir si la réponse à un problème peut être donnée très efficacement, efficacement ou au contraire être inatteignable en pratique, avec des niveaux intermédiaires de difficulté entre les deux extrêmes ; pour cela, elle se fonde sur une estimation – théorique – des temps de calcul et des besoins en mémoire informatique. Dans le but de mieux comprendre comment les problèmes se placent les uns par rapport aux autres, la théorie de la complexité établit des hiérarchies de difficulté entre les problèmes algorithmiques, dont les niveaux sont appelés des « classes de complexité ». Ces hiérarchies comportent des ramifications, suivant que l'on considère des calculs déterministes – l'état suivant du calcul est « déterminé » par l'état courant – ou non déterministes.

Modèles de calcul[modifier | modifier le code]

Une machine de Turing est un modèle de calcul où une tête de lecture/écriture se déplace sur un ruban. On mesure la complexité temporelle par le nombre d'étapes élémentaires de calcul et la complexité spatiale par le nombre de cases du ruban qui sont utilisés durant le calcul.

L'analyse de la complexité est étroitement associée à un modèle de calcul. L'un des modèles de calcul les plus utilisés, car il permet de mesurer le temps de calcul et la mémoire utilisée, est celui de la machine de Turing proposé par Alan Turing en 1936. Un calcul est constitué d'étapes élémentaires. A chaque étape, la machine exécute une action élémentaire (changer d'état interne et déplacer la tête de lecture) en fonction de sa configuration courante (état interne et du symbole lu par la tête de lecture).

D'autres modèles de calcul qui permettent d'étudier la complexité existent :

Mesure de la complexité[modifier | modifier le code]

Les ressources les plus classiques sont le temps et l'espace utilisés.

Généralement, on mesure la quantité de ressources (temps, espace, etc.) requis en fonction de la taille de l'entrée (instance). La façon dont cette taille est mesurée joue un rôle crucial dans l'évaluation de la complexité de l'algorithme. Par exemple, pour le problème de tester si un nombre entier naturel est premier, une instance est un nombre entier naturel. La taille d'un nombre entier naturel se mesure généralement par le nombre de chiffres (par exemple le nombre de bits si le nombre est représenté en binaire). Ainsi, le nombre 1 024 peut être représenté avec seulement onze chiffres binaires et quatre chiffres décimaux et donc sa taille est 11 ou 4 ; la taille d'un entier p vaut alors O(log(p)). La théorie de l'information montre qu'on ne peut diminuer la taille davantage. On mesure la quantité de ressources en fonction de cette taille, qui sera notée n. L'évaluation des ressources requises permet de répartir les problèmes dans des classes de complexité.

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 une machine déterministe résolvant le problème en temps t(n). Le temps est le nombre de transitions sur machine de Turing ou le nombre d’opérations sur machine RAM. En fait, ce temps n'est pas une fonction précise, mais un ordre de grandeur. On parle aussi d'évaluation asymptotique. En particulier les constantes multiplicatives sont systématiquement ignorées grâce au théorème de speedup linéaire. Ainsi, pour un temps qui s'évalue par un polynôme, ce qui compte est le degré du polynôme. Si ce degré est 2, on dira que l'ordre de grandeur est en O(n²), que la complexité est quadratique et que le problème appartient à la classe TIME(n²).

D'autre mesures existent :

Classes de complexité[modifier | modifier le code]

Article détaillé : Classe de complexité.

Une classe de complexité regroupent les problèmes de même complexité. Les classes usuelles sont définies en utilisant les machines de Turing comme modèles de calcul et les ressources sont le temps et l'espace. Le tableau suivant donne quelques exemples de classes de complexité :

Déterministe Non-déterministe
Temps P, EXPTIME NP, NEXPTIME
Espace LOGSPACE, PSPACE, EXPSPACE NLOGSPACE

Problèmes ouverts en théorie de la complexité[modifier | modifier le code]

Le problème ouvert P = NP[modifier | modifier le code]

Article détaillé : Problème P = NP.

On a PNP car un algorithme déterministe est en particulier un algorithme non déterministe. En revanche, la réciproque : NPP, qui est la véritable difficulté de l'égalité P = NP, est un problème ouvert fondamental de l'informatique théorique. Il a été posé en 1970 indépendamment par Stephen Cook et Leonid Levin ; il fait partie des listes, établies en 2000, des problèmes du prix du millénaire et des problèmes de Smale.

La plupart des spécialistes conjecturent que les problèmes NP-complets ne sont pas solubles en temps polynomial (donc, que PNP)[2]. Cela ne signifie pas pour autant que toute tentative de résoudre un problème NP-complet est vaine (voir la section « Résolution » de l'article sur la NP-complétude). Il existe de nombreuses approches (qui se sont finalement révélées irrémédiablement erronées) attaquant le problème PNP ; le spécialiste de la théorie de la complexité Gerhard Woeginger maintient une liste de ces erreurs[3].

La revendication de Vinay Deolalikar (6 août 2010)[4], travaillant aux HP Labs (en), d'une démonstration de PNP, a été la première à faire l'objet d'une attention relativement importante de nombreux mathématiciens et informaticiens de renom, que ce soit sous la forme d'échanges dans des blogs[5],[6],[7], de journaux en ligne ou sous la forme plus construite d'un projet d'étude collaborative en ligne (du type projet Polymath, tel que promu par les médaillés Fields Terence Tao et Tim Gowers). Cette étude collaborative donne la liste des points où l'approche de Vinay Deolalikar achoppe actuellement[8].

Autres problèmes ouverts[modifier | modifier le code]

A l'instar du problème P = NP, on ne sait pas par exemple si :

  • L = NL ?
  • L = P ?
  • NP = co-NP ?
  • P = Pspace ?
  • NP = Pspace ?
  • Exptime = NExptime ?

Relation au coût énergétique[modifier | modifier le code]

La complexité des opérations à réaliser a des conséquences sur leur déroulement concret, notamment la consommation d'énergie nécessaire à leur réalisation. Celle-ci peut varier considérablement suivant la performance des processus utilisés pour effectuer les calculs. En 1961, Rolf Landauer, de la société IBM, a proposé un modèle permettant d'estimer le coût en énergie minimal théorique en donnant une estimation du coût énergétique minimal de changement d'état d'un bit informatique[9]. En date de 2013, cette relation entre complexité et énergie, appelée principe de Landauer, est confirmée par les études expérimentales[10].

Histoire[modifier | modifier le code]

Test de primalité AKS Théorème de Toda Théorème d'Immerman-Szelepcsényi Machine de Turing alternante 21 problèmes NP-complets de Karp Théorème de Cook Théorème de Savitch

Notes[modifier | modifier le code]

  1. En fait, existence constructive et réponse par algorithme vont de pair, et cette exigence est tout à fait naturelle.
  2. William I. Gasarch: Guest Column: the second P =?NP poll. SIGACT News 43(2): 53-77 (2012)
  3. (en) The P-versus-NP page, page personnelle de Gerhard J. Woeginger, de l'université technique d'Eindhoven
  4. (en) Vinay Deolalikar, page personnelle aux HP Labs
  5. (en) Putting my money where my mouth isn't, sur le blog de Scott Aaronson
  6. (en) Gödel's lost letter and P=NP, sur le blog de Dick Lipton
  7. (en) P ≠ NP, sur le blog de Greg Baker & Katrina G. Salvante
  8. (en) Deolalikar P vs NP paper, sur le wiki du projet polymaths
  9. « Tikalon Blog by Dev Gualtieri », Tikalon.com (consulté le 5 mai 2013)
  10. « Landauer Limit Demonstrated - IEEE Spectrum », Spectrum.ieee.org (consulté le 5 mai 2013)

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]