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 un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (temps et/ou espace mémoire) nécessaire pour résoudre un problème algorithmique au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes. Les problèmes sont organisés par classes de complexité.

Problème algorithmique[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 un problème, par exemple le problème du voyageur de commerce. Le problème du voyageur de commerce est la donnée de villes et de distances séparant les villes. Le but étant de trouver un plus court circuit qui passe une et une seule fois par toutes les villes. C'est un problème de recherche d'une solution. 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 ;
  • 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.

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 celui-ci est-il un nombre premier ? »

Instances[modifier | modifier le code]

L'entré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 d'une instance est importante. 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'entrée 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 (indiquez la date de pose grâce au paramètre date).
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. Etant 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 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, ils existent 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és 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 est celui des machines abstraites dans la lignée du modèle proposé par Alan Turing en 1936.

Les deux modèles les plus utilisés en théorie de la complexité sont :

  • la machine de Turing ;
  • la machine RAM (Random Access Machine).

Dans ces deux modèles de calcul, un calcul est constitué d'étapes élémentaires ; à chacune de ces étapes, pour un état donné de la mémoire de la machine, une action élémentaire est choisie dans un ensemble d'actions possibles. Les machines déterministes sont telles que l'action suivante à effectuer est toujours entièrement déterminé par l'état courant de la machine. S'il peut y avoir plusieurs choix possibles d'actions à effectuer, la machine est dite non déterministe. Il peut sembler naturel de penser que les machines de Turing non déterministes sont plus puissantes que les machines de Turing déterministes, autrement dit qu'elles peuvent résoudre en un temps donné des problèmes que les machines déterministes ne savent pas résoudre dans le même temps[2].

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

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

Les mesures les plus classiques de la complexité d'un algorithme sont le temps et l'espace utilisés. D'autre mesures existent, sur les communications par exemple.

Complexité en temps et en espace[modifier | modifier le code]

Généralement, on mesure le temps ou l'espace requis en fonction de la taille de l'instance à traiter. 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). Par exemple, 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. Ainsi, la taille d'un entier p vaut O(log(p)). La théorie de l'information montre qu'on ne peut diminuer la taille davantage. Le but de la théorie de la complexité est de donner une évaluation du temps de calcul ou de l'espace de calcul nécessaire 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. Mais, 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, c'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²).

Autres mesures[modifier | modifier le code]

Selon les modèles de calcul, on peut mesurer d'autres ressources. C'est par exemple le cas dans la théorie de la complexité de la communication ou encore pour les circuits booléens, où le temps et l'espace sont remplacés par la profondeur, la largeur etc.

Classes de complexité[modifier | modifier le code]

Article détaillé : Classe de complexité.

Une classe de complexité contient les problèmes qui ont la même complexité selon un certain critère. Elles font principalement apparaître deux paramètres : un modèle de calcul (par exemple les machines de Turing déterministes) et des contraintes sur les ressources (par exemple le temps pour les machines de Turing). Les classes les plus connues sont des classes définies sur des machines de Turing (déterministes ou non déterministes) avec des contraintes de temps et d'espace. Par exemple, EXPTIME est la classe des problèmes de décision décidés en temps exponentiel sur une machine déterministe.

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)[3]. 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[4]. La revendication de Vinay Deolalikar (6 août 2010)[5], 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[6],[7],[8], 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[9].

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[10]. En date de 2013, cette relation entre complexité et énergie, appelée principe de Landauer est confirmée par les études expérimentales[11].

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. À noter qu'en théorie de la complexité, on parle toujours d'ordre de grandeur.
  3. William I. Gasarch: Guest Column: the second P =?NP poll. SIGACT News 43(2): 53-77 (2012)
  4. (en) The P-versus-NP page, page personnelle de Gerhard J. Woeginger, de l'université technique d'Eindhoven
  5. (en) Vinay Deolalikar, page personnelle aux HP Labs
  6. (en) Putting my money where my mouth isn't, sur le blog de Scott Aaronson
  7. (en) Gödel's lost letter and P=NP, sur le blog de Dick Lipton
  8. (en) P ≠ NP, sur le blog de Greg Baker & Katrina G. Salvante
  9. (en) Deolalikar P vs NP paper, sur le wiki du projet polymaths
  10. « Tikalon Blog by Dev Gualtieri », Tikalon.com (consulté le 5 mai 2013)
  11. « 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]