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é $O(f(n))$ 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 :

• 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 (théorème de hiérarchie en temps déterministe) ;
• 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 $\Pi \leq _{P}\Pi '$ 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. 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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Complexity class » (voir la liste des auteurs).

Lien externe

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