Théorie de la complexité des algorithmes

La théorie de la complexité des algorithmes étudie formellement la quantité de ressources (en temps et en espace) nécessitée par l'exécution d'un algorithme ainsi que la difficulté intrinsèque des problèmes algorithmiques.

Sommaire 1 Histoire 2 Généralités 2.1 Introduction 2.1.1 Exemple de la recherche dans une liste triée 2.1.2 Complexité, comparatif 2.2 Présentation 2.2.1 Problème algorithmique 2.2.2 Réponse algorithmique 2.2.3 Complexité d'un problème algorithmique 2.2.4 De l'existence à la décision 2.3 Modèle de calcul 2.4 Complexité en temps et en espace 3 Classes de complexité 3.1 Classes L et NL 3.2 Classe P 3.3 Classe NP et classe Co-NP (complémentaire de NP) 3.4 Classe PSPACE 3.5 Classe EXPTIME 3.6 Classe NC (Nick's Class) 3.7 Inclusions des classes 4 Problèmes C-complets ou C-difficiles 4.1 Définition 4.2 Exemples 4.3 Réduction de problèmes 4.4 Le problème ouvert P=NP 4.5 Problèmes apparentés 5 Notes 6 Bibliographie 7 Voir aussi 7.1 Articles connexes 7.2 Liens externes

Histoire

Quand les scientifiques se sont posé la question d'énoncer formellement et rigoureusement ce qu'est l'efficacité d'un algorithme ou son contraire sa complexité, ils se sont rendu compte que la comparaison des algorithmes entre eux était nécessaire et que les outils pour le faire à l'époque^[1] étaient primitifs. Dans la préhistoire de l'informatique (les années 1950), la mesure publiée, si elle existait, était souvent dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation et du compilateur utilisé.

Une approche indépendante des facteurs matériels était donc nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The Art of Computer Programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre que, dans le pire cas, il n'est pas possible d'effectuer, sur un ordinateur classique, un tri général (c'est-à-dire uniquement par comparaisons) de N éléments en un temps croissant avec N moins rapidement que N ln N.

Signalons également deux autres directions alternatives à l'analyse de la complexité dans le pire cas, à savoir, la complexité en moyenne (en) des algorithmes qui à partir d'une répartition probabiliste des tailles de données tente d'évaluer le temps moyen que l'on peut attendre de l'évaluation d'un algorithme sur une donnée d'une certaine taille et la complexité amortie des structures de données, qui consiste à déterminer le coût de suites d'opérations.

Généralités

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é 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.

Exemple de la recherche dans une liste triée

Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique qui consiste en une liste triée alphabétiquement. On peut s'y prendre de plusieurs façons différentes. En voici deux :

1. Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché.
2. Recherche dichotomique : ouvrir l'annuaire au milieu, si le nom qui s'y trouve est plus loin alphabétiquement que le nom cherché, regarder avant, sinon, regarder après. Refaire l'opération qui consiste à couper les demi-annuaires (puis les quarts d'annuaires, puis les huitièmes d'annuaires, etc.) jusqu'à trouver le nom cherché.

Pour chacune de ces méthodes il existe un pire cas et un meilleur cas. Prenons la méthode 1 :

• Le meilleur cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé instantanément.
• Le pire cas est celui où le nom est le dernier dans l'annuaire, le nom est alors trouvé après avoir parcouru tous les noms.

Si l'annuaire contient 30 000 noms, le pire cas demandera 30 000 étapes. La complexité dans le pire cas de cette première méthode pour n entrées dans l'annuaire fourni est O(n), ça veut dire que dans le pire cas, le temps de calcul est de l'ordre de grandeur de n  : il faut parcourir tous les n noms une fois.

Le second algorithme demandera dans le pire des cas de séparer en deux l'annuaire, puis de séparer à nouveau cette sous-partie en deux, ainsi de suite jusqu'à n'avoir qu'un seul nom. Le nombre d'étapes nécessaire sera le nombre entier qui est immédiatement plus grand que log ₂n qui, quand n est 30 000, est 15 (car 2¹⁵ vaut 32 768). La complexité (le nombre d'opérations) de ce second algorithme dans le pire des cas^[2] est alors , ce qui veut dire que l'ordre de grandeur du nombre d'opérations de ce pire cas est le logarithme en base 2 de la taille de l'annuaire, c'est-à-dire que pour un annuaire dont la taille est comprise entre 2^{p − 1} et 2^p, il sera de l'ordre de p.

Complexité, comparatif

Pour donner un ordre d'idée sur les différentes complexités, le tableau ci-dessous présente les différentes classes de complexité, leur nom, des temps d'exécution de référence et un problème de la-dite complexité. Les temps d'exécution sont estimés sur la base d'un accès mémoire de 10 nanosecondes par étape. Les temps présentés ici n'ont aucune valeur réaliste car lors d'une exécution sur machine de nombreux mécanismes entrent en jeu. Les temps sont donnés à titre indicatif pour fournir un ordre de grandeur sur le temps nécessaire à l'exécution de tel ou tel algorithme.

Notation	Type de complexité	Temps pour n = 5	Temps pour n = 10	Temps pour n = 20	Temps pour n = 50	Temps pour n = 250	Temps pour n = 1 000	Temps pour n = 10 000	Temps pour n = 1 000 000	Problème exemple
O(1)	complexité constante	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	Accès tableaux
O(log(n))	complexité logarithmique	10 ns	10 ns	10 ns	20 ns	30 ns	30 ns	40 ns	60 ns	Dichotomie
O(n)	complexité linéaire	50 ns	100 ns	200 ns	500 ns	2.5 µs	10 µs	100 µs	10 ms	Parcours de liste
	complexité quasi-linéaire	50 ns	100 ns	200 ns	501 ns	2.5 µs	10 µs	100,5 µs	10 050 µs	Triangulation de Delaunay
O(nlog(n))	complexité linéarithmique	40 ns	100 ns	260 ns	850 ns	6 µs	30 µs	400 µs	60 ms	Tris dont le Tri fusion ou le Tri rapide
O(n2)	complexité quadratique (polynomiale)	250 ns	1 µs	4 µs	25 µs	625 µs	10 ms	1 s	2.8 heures	Parcours de tableaux 2D
O(n3)	complexité cubique (polynomiale)	1.25 µs	10 µs	80 ms	1.25 ms	156 ms	10 s	2.7 heures	316 ans	Parcours de tableaux 3D
O(nlog(n))		30 ns	100 ns	492 ns	7 µs	5 ms	10 s	3.2 ans	1020 ans
O(en)	complexité exponentielle	320 ns	10 µs	10 ms	130 jours	1059 ans	...	...	...	Décomposition en produit de facteurs premiers (cassage de cryptage)
O(n!)	complexité factorielle	1.2 µs	36 ms	770 ans	1048 ans	...	...	...	...	Problème du voyageur de commerce
	complexité doublement exponentielle	4.3 s	10278 ans	...	...	...	...	...	...	Décision de l'arithmétique de Presburger

log ^* (n) est le logarithme itéré.

Présentation

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.

Problème algorithmique

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

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^[4], c'est-à-dire, par exemple, dans le cas du voyageur de commerce, fournissent 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^[5].

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.

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. Le but 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. 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²).

Notation	Type de complexité
O(1)	complexité constante (indépendante de la taille de la donnée)
O(log(n))	complexité logarithmique
	complexité racinaire
O(n)	complexité linéaire
O(nlog(n))	complexité linéarithmique
O(n2)	complexité quadratique
O(n3)	complexité cubique
O(np)	complexité polynomiale
O(en)	complexité exponentielle
O(n!)	complexité factorielle
	complexité doublement exponentielle

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 classes de complexité.

• TIME(t(n)) est 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)) est 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)) est 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)) est 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 de complexité

Dans ce qui suit nous allons définir quelques classes de complexité parmi les plus étudiées en une liste qui va de la complexité la plus basse à la complexité la plus haute. Il faut cependant avoir à l'esprit que ces classes ne sont pas totalement ordonnées.

Commençons par la classe constituée des problèmes les plus simples, à savoir : ceux dont la réponse peut être donnée en temps constant. Par exemple, la question de savoir si un nombre entier est positif peut être résolue sans vraiment calculer, donc en un temps indépendant de la taille du nombre entier. C'est la plus basse des classes de problèmes.

La classe des problèmes linéaires est celle qui contient les problèmes qui peuvent être décidés en un temps qui est une fonction linéaire de la taille de la donnée. Il s'agit des problèmes qui sont en O(n).

Souvent au lieu de dire : « un problème est dans une certaine classe C », on dit plus simplement : « le problème est dans C ».

Classes L et NL

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. Avec les notations introduites plus haut, L = SPACE(log(n)). La classe NL s'apparente à la classe L mais sur une machine non déterministe (NL = NSPACE(log(n)). Par exemple, savoir si un élément appartient à un tableau trié peut se faire en espace logarithmique.

Classe P

Un problème de décision est dans P s'il peut être décidé sur une machine déterministe en temps polynomial par rapport à la taille de la donnée. On qualifie alors le problème de polynomial. C'est un problème de complexité O(n^k), pour un certain k.

Un exemple de problème polynomial est celui de la connexité dans un graphe. Étant donné un graphe à s sommets (on considère que la taille de la donnée, donc du graphe, est son nombre de sommets), il s'agit de savoir si toutes les paires de sommets sont reliées par un chemin. Un algorithme de parcours en profondeur construit un arbre couvrant du graphe à partir d'un sommet. Si cet arbre contient tous les sommets du graphe, alors le graphe est connexe. Le temps nécessaire pour construire cet arbre est au plus c.s² (où c est une constante et s le nombre de sommets du graphe), donc le problème est dans la classe P.

On admet, en général, que les problèmes dans P sont ceux qui sont facilement résolubles^[6].

Classe NP et classe Co-NP (complémentaire de NP)

La classe NP des problèmes Non-déterministes Polynomiaux réunit les problèmes de décision qui peuvent être décidés sur une machine non déterministe en temps polynomial. De façon équivalente, c'est la classe des problèmes qui admettent un algorithme polynomial capable de tester la validité d'une solution du problème — on dit aussi : capable de construire un certificat. Intuitivement, les problèmes dans NP sont les problèmes qui peuvent être résolus en énumérant l'ensemble des solutions possibles et en les testant à l'aide d'un algorithme polynomial.

Par exemple, la recherche de cycle hamiltonien dans un graphe peut se faire par l'enchainement de deux algorithmes :

• le premier engendre l'ensemble des cycles (en temps exponentiel, classe EXPTIME, voir ci-dessous) ;
• puis le second teste les solutions (en temps polynomial).

Ce problème est donc dans la classe NP.

La classe duale de la classe NP, qui s'intéresse à la négation de la propriété donnée, est appelée Co-NP.

Classe PSPACE

La classe PSPACE est celle des problèmes décidables par une machine déterministe en espace polynomial par rapport à la taille de sa donnée. On peut aussi définir la classe NSPACE ou NPSPACE des problèmes décidables par une machine non déterministe en espace polynomial par rapport à la taille de sa donnée. Par le théorème de Savitch, on a PSPACE = NPSPACE, c'est pourquoi on ne rencontre guère les notations NSPACE ni NPSPACE.

Classe EXPTIME

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

Classe NC (Nick's Class)

La classe NC est la classe des problèmes qui peuvent être résolus en temps poly-logarithmique (c'est-à-dire résolus plus rapidement qu'il ne faut de temps pour lire séquentiellement leurs entrées) sur une machine parallèle ayant un nombre polynomial (c'est-à-dire raisonnable) de processeurs.

Intuitivement, un problème est dans NC s'il existe un algorithme pour le résoudre qui peut être parallélisé et qui gagne à l'être. C'est-à-dire, si la version parallèle de l'algorithme (s'exécutant sur plusieurs processeurs) est significativement plus efficace que la version séquentielle.

Par définition, NC est un sous ensemble de la classe P (NC P) car une machine parallèle peut être simulée par une machine séquentielle.

Mais on ne sait pas si P NC (et donc si NC = P). On conjecture que non, en supposant qu'il existe dans P des problèmes dont les solutions sont intrinsèquement non parallélisables.

Inclusions des classes

On a les inclusions :

• P NP, et symétriquement P Co-NP
• NP PSPACE = NPSPACE, et Co-NP PSPACE.

En effet, un problème polynomial peut se résoudre en engendrant une solution et en la testant à l'aide d'un algorithme polynomial. Tout problème dans P est ainsi dans NP.

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é 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 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 à Π. 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 dans P, c'est-à-dire que l'algorithme qui calcule le passage d'une instance de Π' à une instance de Π est polynomial (voir Réduction polynomiale). 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. On a par la suite établi la NP-complétude de nombreux autres problèmes.

On qualifie de NP-complets les problèmes décisionnels, c'est-à-dire ceux dont la réponse est de type binaire (oui/non, vrai/faux, 1/0, …). On qualifie de NP-difficiles les problèmes d'optimisation, c'est-à-dire que la réponse est de type numérique. À un problème d'optimisation NP-difficile est associé un problème de décision NP-complet, mais dire qu'un problème NP-difficile est aussi NP-complet est un abus de langage.

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.

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). 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^[7]. La revendication récente (6 août 2010) de Vinay Deolalikar^[8], 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^{[9],[10],[11]}, de journaux en ligne ou sous la forme plus construite d'un projet d'étude collaborative en ligne (du type Polymath project (en), 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^[12].

Problèmes apparentés

• On ne sait pas si L = NL.

• On sait que PSPACE = NPSPACE.

• Pour résumer, on a L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME.

On sait de plus que NL ⊊ PSPACE. Donc deux classes au moins entre NL et PSPACE ne sont pas égales. On sait également que P ≠ EXPTIME.

Notes

Bibliographie

• O. Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4)
• (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 0-201-53082-1)
• (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
• (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

v · d · m Informatique théorique
Théorie du calcul	Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Ensemble récursivement énumérable Modèle de calcul Automate fini •Transducteur fini •Automate sur les mots infinis •Automate à pile •Automate linéairement borné • Automate cellulaire • Machine de Turing • Thèse de Church Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet
Logique, syntaxe et sémantique	Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Transduction rationnelle • Langage rationnel • Langage algébrique • Langage contextuel • Théorie des langages Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking
Algorithmique, complexité et mathématiques discrètes	Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (structure de données) • Liste (informatique) • Table de hachage • Tas (informatique) Théorie des graphes Coloration de graphe • Problèmes de cheminement Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement Données et codage Combinatoire des mots •Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

• Portail de l’informatique
• Portail de l'informatique théorique