Théorie de la complexité

Infos
La théorie de la complexité étudie formellement la difficulté intrinsèque des problèmes algorithmiques.
Théorie de la complexité

La théorie de la complexité étudie formellement la difficulté intrinsèque des problèmes algorithmiques.

Généralités

Présentation

La théorie de la complexité s'attache à connaitre la difficulté (ou la complexité) d'une réponse par algorithme à un problème posé de façon mathématique. Pour pouvoir la définir, il faut présenter ces trois concepts que sont les problèmes algorithmiques, les réponses algorithmiques aux problèmes, la complexité des problèmes algorithmiques.

Problème algorithmique

Un problème algorithmique est 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). Ces problème comporte des hypothèses et des données et une question. On distingue deux types de problèmes:
- les problèmes de décision ont une question dont la réponse est oui ou non,
- les problèmes d'existence ou de recherche d'une solution comporte 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 est 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 s'occupe que de 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 inatteignables en pratique, avec entre les deux extrêmes des niveaux intermédiaires de difficulté ; 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 une hiérarchie de difficulté entre les problèmes algorithmiques, dont les niveaux sont appelés des « classes de complexité ». Cette hiérarchie comporte 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èle de calcul

L'analyse de la complexité est étroitement associé à un modèle de calcul. L'un de modèles de calcul les plus utilisés est celui des machines abstraites dans la lignée du modèle proposé par 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 calul, 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 possible 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 tempsA noter qu'en théorie de la complexité on parle toujours d'ordre de grandeur.. D'autres modèles de calcul qui permettent d'étudier la complexité s'appuient sur la logique linéaire (lambda calcul linéaire) et les types.

Complexité en temps et en espace

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 \complement ^2 _s : il y a \complement ^2 _s arêtes possibles dans un tel graphe, et pour chacune, on doit utiliser un bit pour dire si elle est effectivement présente dans le graphe. On peut par exemple choisir une représentation matricielle (il y aura \complement ^2 _s cellules dans la matrice à stocker et chacune vaudra 0 ou 1).
- la taille d'un vecteur d'éléments à 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)) = 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)) = La complexité en espace évalue l'espace mémoire utilisé en fonction de la taille des données ; elle est définie de manière analogue :
- SPACE(s(n)) =
- NSPACE(s(n)) =

Le problème du codage

Le codage influence la complexité des problèmes. Il est bon de se rappeler que les données sur lesquelles travaillent les algorithmes sont nécessairement stockées 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 initiale, l'ensemble des complexités des algorithmes sera sans doute caché par la complexité du codage : il faut par exemple s'interdire de coder le résultat dans l'entrée... On ne s'intéressera ici qu'aux codages raisonnables.

Problème de décision

Chaque problème informatique peut se réduire à un problème de décision, c’est-à-dire un problème formulé comme une question dont la réponse est Oui ou Non, plutôt que par exemple la taille du plus court chemin est 42. Un problème qui n'est pas formulé de cette manière peut être très simplement transformé en un problème de décision équivalent. 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 B \in \mathbb. Ce problème 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.

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 s'apparente à 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 le problème de la connexité dans un graphe. Étant donné un graphe à s sommets, il s'agit de savoir si toutes les paires de sommets sont reliées par un chemin. Pour le résoudre, on dispose de l'algorithme de parcours en profondeur qui va construire 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 s^2, donc le problème est bien dans la classe P. Les problèmes dans P correspondent en fait à tous les problèmes facilement solubles.

Classe NP

Un problème NP est Non-déterministe Polynomial (et non pas Non polynomial, erreur très courante). La classe NP réunit les 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 admettent un algorithme dans P qui, étant donné une solution du problème NP (un certificat), est 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 (en temps polynomial).

Classe Co-NP (Complémentaire de NP)

C'est le nom parfois donné pour l'équivalent de la classe NP, mais avec la réponse non.

Classe PSPACE

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

Classe NSPACE ou NPSPACE

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

Classe LOGSPACE

Classe EXPTIME

Elle rassemble 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 \subset NP, et symétriquement P \subset Co-NP
- NP \subset PSPACE = NPSPACE, et Co-NP \subset PSPACE. 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 dans P est aussi dans NP. La recherche travaille activement à déterminer si NP \subset P (concluant à P = NP) ou si, au contraire P \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, et
- 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 \Pi et \Pi' deux problèmes ; Une réduction de \Pi' à \Pi est un algorithme transformant toute instance de \Pi' en une instance de \Pi. Ainsi, si l'on a un algorithme pour résoudre \Pi, on sait aussi résoudre \Pi'. \Pi est donc au moins aussi difficile à résoudre que \Pi'. \Pi est alors C-difficile si pour tout problème \Pi' de C, \Pi' se réduit à \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 \Pi' à une instance de \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

Pour montrer qu'un problème \Pi est C-difficile pour une classe C donnée, il y a deux façons de procéder: montrer que tout problème de C se réduit à \Pi, ou bien il suffit de montrer qu’un problème C-difficile se réduit à \Pi. C'est cette deuxième méthode, plus facile, qui est utilisée dès que l'on dispose d'au moins un problème C-complet.

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 évidente un algorithme pour le résoudre avec une machine non déterministe, par exemple en énonçant tous les cycles puis en sélectionnant le plus court.
- Nous disposons du problème de la recherche de cycle hamiltonien pour les graphes non orientés. Un graphe non orienté peut se transformer en un graphe orienté en « doublant » chaque arête de manière à obtenir, pour chaque paire de nœuds adjacents, des chemins dans les deux sens. Il est donc possible de ramener le problème connu, 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. L'établissement d'un « premier » problème NP-complet pour classer tous les autres s'est toutefois avéré nécessaire : Ainsi le théorème de Cook (de Stephen Cook) 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.

Listes

- 21 problèmes NP-complets de Karp
- Liste de problèmes NP-complets

Le problème ouvert P=NP

On a trivialement \mbox \subseteq \mbox 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 : \mbox \subseteq \mbox, qui est la véritable difficulté de l'égalité \mbox = \mbox est l'un des problèmes ouverts les plus fondamentaux et intéressants en informatique théorique. Il a été posé en 1970 indépendamment par Stephen Cook et Leonid Levincelui qui arrivera à décider si P et NP sont différents ou égaux recevra le prix Clay de plus de 1 000 000 $. Ce problème fait partie des problèmes du prix du millénaire qui compte 7 défis mathématiques réputés insurmontables. La résolution de chacun d'entre eux est assortie d'un prix d'un million de dollars étasuniens. . La plupart des spécialistes conjecturent que les problèmes NP-complets ne sont pas solubles en un temps polynomial. À partir de là plusieurs approches ont été 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, sans savoir s'il s'agit de la meilleure solution ;
- Des algorithmes stochastiques : en utilisant des nombres aléatoires on peut «forcer» un algorithme à ne pas utiliser les cas les moins favorables, l'utilisateur devant préciser une probabilité maximale admise que l'algorithme fournisse un résultat erroné. Citons notamment comme application des algorithmes de test de primalité en temps polynomial en la taille du nombre à tester. A noter qu'un algorithme polynomial non stochastique a été proposé pour ce problème en août 2002 par Agrawal, Kayal et Saxena ;
- 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.

Autres problèmes apparentées

Pour le cas de L et NL, on ne sait pas non plus si \mbox = \mbox. Mais cette question est moins primordiale car \mbox \subseteq \mbox \subseteq \mbox \subseteq \mbox. De fait, les problèmes dans L et dans NL sont solubles efficacement. Inversement on sait que \mbox = \mbox. Par contre \mbox \subseteq \mbox. Donc, avant de résoudre \mbox = \mbox, il faut résoudre \mbox = \mbox. Pour résumer, on a \mbox \subseteq \mbox \subseteq \mbox \subseteq \mbox \subseteq \mbox = \mbox \subseteq \mbox \subseteq \mbox. On sait de plus que NL est strictement inclus dans PSPACE. Donc deux classes au moins entre NL et PSPACE ne sont pas égales. On sait également que \mbox \neq \mbox.

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

Notes et références de l'article


- , annexe C « A Computational Toolkit », pp. 504-515
- 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

Voir aussi

===
Sujets connexes
Algorithme de parcours en profondeur   Algorithmique   Automate cellulaire   Calcul des prédicats   Calculabilité   Clique (théorie des graphes)   Coloration de graphe   Fonction récursive   Graphe hamiltonien   Heuristique   Informatique   Lambda-calcul   Lexique de la théorie des graphes   Liste de problèmes NP-complets   Logique linéaire   Machine de Turing   Machine de Turing non déterministe   Mémoire informatique   Problème SAT   Problème du voyageur de commerce   Réduction polynomiale   Stephen Cole Kleene   Stephen Cook   Séparation et évaluation   Test de primalité   Test de primalité AKS   Théorie des types   Théorème de Cook  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^