Accueil🇫🇷Chercher

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.

Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée.

Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP.

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 dĂ©cidĂ©s en temps polynomial par une machine dĂ©terministe. Ces problèmes sont souvent considĂ©rĂ©s comme ceux pour lesquels il existe un algorithme efficace (voir la thèse de Cobham) ;
  • NP, la classe des problèmes dĂ©cidĂ©s en temps polynomial par une machine non dĂ©terministe (ainsi que la classe complĂ©mentaire, co-NP) ;
  • EXPTIME, la classe des problèmes dĂ©cidĂ©s en temps exponentiel par une machine dĂ©terministe ;
  • NEXPTIME, la classe des problèmes dĂ©cidĂ©s en temps exponentiel par 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 :

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 :

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[1]. 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.

Notes et références

  1. Michel Serfati (dir.), De la méthode : recherches en histoire et philosophie des mathématiques, PUFC, coll. « Colloques et séminaires », (ISBN 2848670002, lire en ligne), « Machine de Turing et complexité algorithmique », p. 206.

Lien externe

« Complexity Zoo », sur université de Waterloo, un wiki répertoriant un grand nombre de classes de complexité.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.