Accueil > Hypercomplex > Théorie de la complexité

Théorie de la complexité

mardi 19 septembre 2006, par Petit poney

La théorie de la complexité s’intéresse à l’étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s’attache à savoir si un problème peut ou pas être résolu par un ordinateur.

La théorie de la complexité se concentre donc sur les problèmes qui peuvent effectivement être résolus, la question étant de savoir s’ils peuvent être résolus efficacement ou pas en se basant sur une estimation (théorique) des temps de calcul et des besoins en mémoire informatique.

Généralités :

En théorie de la complexité, un problème est formalisé de la manière suivante : un ensemble de données (ou instance) en entrée, et une question sur ces données (pouvant demander éventuellement un calcul). La théorie de la complexité ne traite que des problèmes de décision binaire, c’est-à-dire posant une question dont la réponse soit oui ou non. Cependant on étend la notion de complexité aux problèmes d’optimisation. En effet il est facile de transformer un problème d’optimisation en problème de décision. Si par exemple on cherche à optimiser une valeur n on traite le problème de décision qui consiste à comparer n à un certain k. En traitant plusieurs valeurs de k on peut déterminer une valeur optimale. On confondra souvent un problème d’optimisation et son problème de décision associé.

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. Parmi les classes les plus courantes, on distingue :

- 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 correspond à 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.
- Classe NP : c’est la classe des 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.
- Classe Co-NP : nom parfois donné pour l’équivalent de la classe NP avec la réponse non.
- Classe PSPACE : les problèmes décidables par un algorithme déterministe en espace polynomial par rapport à la taille de son instance.
- Classe NSPACE ou NPSPACE : les problèmes décidables par un algorithme non-déterministe en espace polynomial par rapport à la taille de son instance.
- Classe EXPTIME : les problèmes décidables par un algorithme déterministe en temps exponentiel par rapport à la taille de son instance.

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
* 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 p et q deux problèmes, une réduction de q à p est un algorithme transformant toute instance de q en une instance de p. Ainsi, si l’on a un algorithme pour résoudre p, on sait aussi résoudre q. p est donc au moins aussi difficile à résoudre que q.

p est alors C-difficile si pour tout problème q de C, q se réduit à p. 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 q à une instance de p est polynomial. Quand on parle de problèmes P-difficiles on s’autorise uniquement des réductions dans LOGSPACE.

Problème NP-Complet  :

Les problèmes complets les plus étudiés sont les problèmes NP-complets. Ceci parce que beaucoup de problèmes intéressants sont NP-complets et que l’on ne sait pas résoudre un problème NP-complet efficacement à cause du non déterminisme. 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.

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 celullaires
- les automates à pile
- les machines à registres (RAM)
- le lambda-calcul
- le calcul quantique

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 je suis derrière mon clavier en ce moment : on peut construire des ordinateurs.



Voir en ligne : Wikipedia.org

Répondre à cet article