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

Pour les articles homonymes, voir Théorie de la complexité.

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 (en temps et en espace) nécessaire pour la résolution de problèmes au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes posés mathématiquement.

Introduction

Un algorithme répond à un problème. Il est composé d'un ensemble d'étapes simples nécessaires à la résolution, dont le nombre varie en fonction du nombre d'éléments à traiter. D'autre part, plusieurs algorithmes peuvent répondre à un même problème. Pour savoir quelle méthode est plus efficace il faut les comparer. Pour cela, on utilise une mesure que l'on appelle la complexité en temps qui représente le nombre d'étapes qui seront nécessaires pour résoudre le problème pour une entrée de taille donnée.

La théorie de la complexité s'attache à connaître la difficulté (ou la complexité) d'une réponse par algorithme à un problème, dit algorithmique, posé de façon mathématique. Pour la définir, il faut présenter les concepts de problèmes algorithmiques, de réponses algorithmiques aux problèmes, et la complexité des problèmes algorithmiques.

Définition

Un problème algorithmique est un problème posé de façon mathématique, c'est-à-dire qu'il est énoncé rigoureusement dans le langage des mathématiques – le mieux étant d'utiliser le calcul des prédicats. Il comprend des hypothèses, des données^[1] et une question. 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écisions.

Exemple de problème

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

"Étant donné un entier n celui-ci est-il un nombre premier ?"

Réponse algorithmique

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 est décidable s'il s'agit d'un problème de décision – donc d'un problème dont la réponse est soit oui soit non – et si sa réponse peut être fournie par un algorithme. Symétriquement, un problème est calculable s'il s'agit d'un problème d'existence et si l'élément calculé peut être fourni 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

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 (et en théorie), 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.

De l'existence à la décision

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^[2], 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.

Modèle de 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 chaque action possible est unique, c'est-à-dire que l'action à effectuer est dictée de façon unique par l'état courant de celle-ci. 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^[3].

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

• les fonctions récursives, dues à Kleene ;
• le lambda-calcul ;
• les automates cellulaires ;
• la logique linéaire.

Mesure de la complexité

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

Sans nuire à la généralité on peut supposer que les problèmes que nous considérons n'ont qu'une donnée. Cette donnée a une taille qui est un nombre entier naturel. La façon dont cette taille est mesurée joue un rôle crucial dans l'évaluation de la complexité de l'algorithme. Ainsi, si la donnée est elle-même un nombre entier naturel, sa taille peut être appréciée de plusieurs façons : on peut dire que la taille de l'entier p vaut p, mais on peut aussi dire qu'elle vaut log(p) parce que l'entier a été représenté en numération binaire ou décimale, ce qui raccourcit la représentation des nombres. Ainsi, 1 024 peut être représenté avec seulement onze chiffres binaires et quatre chiffres décimaux et donc sa taille est 11 ou 4, et non pas de l'ordre de 1 000. En pratique, c'est cette deuxième taille qui est utilisée, à la fois parce qu'elle correspond à la représentation usuelle des données sur une machine, et parce que la théorie de l'information montre qu'on ne peut essentiellement pas la diminuer encore. 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

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é

Les classes de complexité sont des ensembles de problèmes qui ont la propriété d'avoir tous la même complexité selon un certain critère. Les définitions des classes usuelles (pour les problèmes de décision) font principalement apparaître deux paramètres : un modèle de calcul (par exemple les machines de Turing) 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.

Les quatre familles de classes de complexité en temps et en espace

Suivant qu'il s'agit de temps et d'espace, de machine déterministes ou non déterministes, on distingue quatre familles principales de classes de complexité :

TIME(t(n))

La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine déterministe.

NTIME(t(n))

La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine non déterministe.

SPACE(s(n))

La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine déterministe.

NSPACE(s(n))

La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine non déterministe.

Classes en temps

Les classes en temps classiques sont :

• P, la classe des problèmes qui peuvent être résolus en temps polynomial sur une machine déterministe. Ces problèmes sont souvent considérés comme ceux pour lesquels il existe un algorithme efficace ;
• NP, la classes des problèmes qui peuvent être résolus en temps polynomial sur une machine non déterministe. La classe complémentaire, co-NP, apparait aussi de façon naturelle ;
• EXPTIME, la classe des problèmes qui peuvent être résolus en temps exponentiel sur une machine déterministe ;
• NEXPTIME, la classe des problèmes qui peuvent être résolus en temps exponentiel sur une machine non-déterministe.

Classes en espace

Les classes classiques pour des contraintes d'espace sont :

• L, la classe des problèmes qui peuvent être résolus en espace logarithmique sur une machine déterministe ;
• NL, la classe des problèmes qui peuvent être résolus en espace logarithmique sur une machine non-déterministe ;
• PSPACE, la classe des problèmes qui peuvent être résolus en espace polynomial sur une machine déterministe. En fait cette classe est égale à NPSPACE d'après le théorème de Savitch ;
• EXPSPACE, la classe des problèmes qui peuvent être résolus en espace exponentiel. Cette classe est égale à NEXPSPACE d'après le théorème de Savitch.

Autres classes

Parmi les autres classes de complexité, on peut citer celles qui utilisent un autre modèle de calcul, comme :

• les circuits booléens, avec les classes NC et P/poly par exemple, qui permettent de modéliser le calcul parallèle et d'obtenir des bornes inférieures plus facilement ;
• les modèles probabilistes, qui utilisent des machines de Turing probabilistes, et permettent de modéliser les algorithmes randomisés, avec les classes ZPP, RP et BPP notamment ;
• ou encore les classes quantiques comme BQP, les classes issues de la cryptographie comme IP (dans le cadre des systèmes de preuves interactives) ou PCP…

Inclusions des classes

On a les inclusions :

• L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE ;
• P ⊆ Co-NP ⊆ PSPACE.

Les théorèmes de hiérarchie assurent que :

• NL ⊊ PSPACE ⊊ EXPSPACE ;
• P ⊊ EXPTIME ;
• NP ⊊ NEXPTIME.

En revanche, on ne sait pas aujourd'hui ce qu'il en est des inclusions plus fortes.

Problèmes C-complets ou C-difficiles

Définition

Soit C une classe de complexité (comme P, NP, PSPACE, etc.). On dit qu'un problème est C-difficile si ce problème est au moins aussi difficile que tous les problèmes dans C. Un problème C-difficile qui appartient à C est dit C-complet.

Formellement, on définit une notion de réduction : soient Π et Π' deux problèmes ; une réduction de Π' à Π est un algorithme (ou une machine) d'une complexité donnée (qu'on sait être inférieure à celle de la classe) C transformant toute instance de Π' en une instance de Π. Ainsi, si l'on a un algorithme pour résoudre Π, on sait aussi résoudre Π'. On peut donc dire que Π est au moins aussi difficile à résoudre que Π', à la complexité de la réduction près.

Π est alors C-difficile si pour tout problème Π' de C, Π' se réduit à Π. La notion de C-difficile peut varier selon le type de complexité que l'on autorise pour la réduction. Dans beaucoup de cas on s'intéresse aux réductions polynomiales, c'est-à-dire celle demandant uniquement un espace et un temps polynomial pour être effectuée. Mais on peut également s'intéresser à d'autres types de réductions comme celles utilisant un espace logarithmique, afin d'étudier par exemple le lien entre les classes P et L.

La relation de réduction étant réflexive et transitive, elle définit un pré-ordre sur les problèmes. Ainsi, on la note usuellement avec le symbole ≤ : on a Π'≤Π si Π' se réduit à Π. On peut apposer au symbole une lettre précisant le type de réduction que l'on s'autorise: par exemple signifie habituellement qu'il existe une réduction polynomiale de Π vers Π'. Les problèmes C-difficiles sont les majorants de C et les problèmes C-complets sont les plus grands éléments de C.

Exemples

Les problèmes NP-complets sont un cas particulier important de ce concept. De manière standard, ils sont définis en autorisant uniquement des réductions polynomiales, c'est-à-dire que l'algorithme qui calcule le passage d'une instance de Π' à une instance de Π est polynomial. Le théorème de Cook-Levin, dû à Stephen Cook et à Leonid Levin, énonce qu'il existe un problème NP-complet. Plus précisément, Cook a montré que le problème SAT est NP-complet^[4]. On a par la suite établi la NP-complétude de nombreux autres problèmes.

Quand on parle de problèmes P-complets ou P-difficiles on s'autorise uniquement des réductions dans LOGSPACE.

Réduction de problèmes

Pour montrer qu'un problème Π est C-difficile pour une classe C donnée, il y a deux façons de procéder : ou bien montrer que tout problème de C se réduit à Π, ou bien montrer qu’un problème C-complet se réduit à Π. Par exemple, démontrons avec la seconde méthode que le problème de la recherche de circuit hamiltonien dans un graphe orienté est NP-complet.

• Le problème est dans NP, autrement dit, il peut être résolu par un algorithme polynomial sur une machine non déterministe. Il suffit par exemple d'engendrer de façon non déterministe un circuit, puis de tester s'il est hamiltonien.
• On sait que le problème de la recherche d'un cycle hamiltonien dans un graphe non orienté est NP-difficile. Or un graphe non orienté peut se transformer en un graphe orienté en créant deux arcs opposés pour chaque arête. Il est donc possible de ramener le problème connu, NP-complet, à savoir chercher un cycle hamiltonien dans un graphe non orienté, au problème que nous voulons classer, à savoir chercher un circuit hamiltonien dans un graphe orienté. Le problème de l'existence d'un circuit hamiltonien est donc NP-complet.

Problèmes ouverts en théorie de la complexité

Le problème ouvert P=NP

On a clairement P ⊆ NP car un algorithme déterministe est un algorithme non déterministe particulier, ce qui, dit en mots plus simples, signifie que si une solution peut être calculée en temps polynomial, alors elle peut être vérifiée en temps polynomial. En revanche, la réciproque : NP ⊆ P, 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 un temps polynomial (donc, que P ≠ NP)^[5]. 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 P ≠ NP ; le spécialiste de la théorie de la complexité Gerhard Woeginger maintient une liste de ces erreurs^[6]. La revendication de Vinay Deolalikar (6 août 2010)^[7], travaillant aux HP Labs (en), d'une démonstration de P ≠ NP, 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^[8],[9],[10], 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^[11].

Autres problèmes

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

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

Notes

1. ↑ Les données sont aussi appelées des instances.
2. ↑ En fait, existence constructive et réponse par algorithme vont de pair, et cette exigence est tout à fait naturelle.
3. ↑ À noter qu'en théorie de la complexité, on parle toujours d'ordre de grandeur.
4. ↑ Michel Serfati (dir.), De la méthode : recherches en histoire et philosophie des mathématiques, PUFC, coll. « Colloques et séminaires »,‎ 2002 (ISBN 2848670002, lire en ligne), « Machine de Turing et complexité algorithmique », p. 206.
5. ↑ William I. Gasarch: Guest Column: the second P =?NP poll. SIGACT News 43(2): 53-77 (2012)
6. ↑ (en) The P-versus-NP page, page personnelle de Gerhard J. Woeginger, de l'université technique d'Eindhoven
7. ↑ (en) Vinay Deolalikar, page personnelle aux HP Labs
8. ↑ (en) Putting my money where my mouth isn't, sur le blog de Scott Aaronson
9. ↑ (en) Gödel's lost letter and P=NP, sur le blog de Dick Lipton
10. ↑ (en) P ≠ NP, sur le blog de Greg Baker & Katrina G. Salvante
11. ↑ (en) Deolalikar P vs NP paper, sur le wiki du projet polymaths
12. ↑ « Tikalon Blog by Dev Gualtieri », Tikalon.com (consulté le 5 mai 2013)
13. ↑ « Landauer Limit Demonstrated - IEEE Spectrum », Spectrum.ieee.org (consulté le 5 mai 2013)

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité,‎ 2008 [détail de l’édition] (lire en ligne)
• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7)
• (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley,‎ 1993 (ISBN 978-0-201-53082-7)
• (en) Michael R. Garey et David S. Johnson, Computers and Intractability : A guide to the theory of NP-completeness, W.H. Freeman & Company, 1979 (ISBN 0-7167-1045-5)
• Richard Lassaigne et Michel de Rougemont, Logique et Complexité, Hermes, 1996 (ISBN 2-86601-496-0)
• Nicolas Hermann et Pierre Lescanne, Est-ce que P = NP ? Les Dossiers de La Recherche, 20:64–68, août-octobre 2005

Voir aussi

Articles connexes

• Complexité, article général sur la complexité
• Complexité de Kolmogorov
• Explosion combinatoire
• Machine de Turing non déterministe
• Réduction polynomiale

Liens externes

• (en) Complexity Zoo consulté le 21 avril 2014
• (en) The Status of the P versus NP Problem : cet article, publié dans les Comm. of the ACM, a été cité par l'article New York Times ci-dessous.
• (en) « Prizes Aside, the P-NP Puzzler Has Consequences », The New York Times, 7 octobre 2009

• Portail de l’informatique
• Portail de l'informatique théorique
• Portail des mathématiques