21/05/2007

Les classes P et P Complete

 

Les classe P et P Complete – Complexité structurelle

Introduction

Dans la théorie de la complexité, P est une classe de complexité contenant des problèmes de décision qui peuvent être résolu par une machine de Turing déterministe en temps polynomial.

On appelle temps polynomial le temps de calcul d’un problème qui dépendrait de la taille du problème, on le note en mathématique : O(nk) ou k est une constante qui dépend du problème et n la taille du problème.

P est connu pour être la classe de problème ‘qui se résout efficacement’. Cependant il existe des problèmes de classe P qui ne se résolvent pas si facilement (par exemple un temps de calcul en n^1000000). Nous allons donc détailler un peu plus les problèmes de classe P.

 

Les problèmes types de la classe P

On retrouve dans la classe de complexité P des problèmes communs comme le calcul du plus grand diviseur commun, trouver un matching maximum. En 2002, il y a été prouve que déterminer si un nombre est premier est dans la classe P.

Une explication simple pour la P-complétude est la suivante : un problème A est dans la classe P-complet si pour chaque problème B dans P il existe des constantes c et k qui permettent de réduire B en A en temps O((log n)c) en utilisant O(nk) processeurs parallèles.

On retrouve dans cette classe certains problèmes connus comme :

· L’algorithme LZW.

· En programmation linéaire, la maximisation d’une fonction linéaire sous contraintes.

· Le jeu de la vie, a la façon de Conway, on prend une cellule et un temps T, cette cellule sera-t-elle vivante après T étapes ?

Il existe beaucoup d’autres problèmes appartenant a cette classe, le but de ce pamphlet n’est pas de tous les lister.

De manière générale pour prouver qu’un problème est P-complet, on essaye de réduire un problème que l’on sait être P-complet a ce problème.

Propriétés

La première propriété est que la classe P est minimum pour elle-même. C'est-à-dire que .

La classe P est en fait indépendant de tout modèle ou machine, car par exemple P est identique sur une machine de Turing à simple ou multi-bandes, ainsi que si les accès se font aléatoirement. En effet, tout cela peut être simulé en temps polynomial.

Tout langage de P peut être exprimé comme une formule du premier ordre associée à un ordonnancement et un opérateur minimal.

Accessibilité et relations avec les autres classes

 

La classe P, comme nous l’avons vu contient les problèmes décidables par une machine de Turing en temps polynomial. Par la même, nous sous-entendons que P signifie « facile », bien que cette idée soit raisonnable et pertinente en complexité structurelle, ce n’est pas toujours le cas en pratique.

Dans cette partie, nous nous intéresseront dans un premier temps à l’accessibilité de la classe P puis nous détaillerons le lien qui existe entre P et deux des classes les plus connu et les plus conséquentes, NP (problèmes non déterministes) et L (problèmes logarithmiques).

· P est elle une classe accessible en pratique ?

Les problèmes situés dans la classe P se résolvent en un temps polynomial, il est donc logique de considérer qu’en pratique leur résolution s’effectue rapidement. Seulement un certains nombre de caractéristiques de P en font une classe pas toujours accessible en pratique.

Par exemple, la classe P ignore les facteurs constants. Ainsi, «  n » est en temps linéaire et appartient à P mais reste inaccessible dans la pratique. De même, la taille de l’exposant n’est pas pris en compte, un problème en «  » est dans P mais absolument pas accessible.

Par ailleurs, en complexité structurelle, les temps de résolutions des problèmes sont toujours considérés selon le pire scénario, certains problèmes qui pourrait être vu en pratique comme étant de classe P sont donc en théorie classé dans des classes plus complexe. Ainsi, il peut arriver qu’en pratique, un problème soit le plus souvent résolue en temps linéaire tandis qu’en de rares occasions une instance du problème requiert un temps exponentiel. Un tel problème possède en moyenne un temps de résolution polynomiale seulement il n’appartient pas à la classe P.

· Classe NP

Une généralisation de la classe P est la classe NP, il s’agit des problèmes en temps polynomiaux sur une machine de Turing non déterministe. Ainsi, P est un sous-ensemble de NP.

En revanche, il appartient toujours au domaine de la recherche de prouver que ce sous-ensemble est strique ou bien au contraire une égalité. Les deux partis possèdent chacun des arguments qui jusqu’à ce jour ne constituent pas de preuves concrètent.

· Classe L

En complexité structurelle, il est connu que P est au moins aussi large que la classe des problèmes décidables en taille mémoire logarithmique, L. En effet, un solver utilisant de mémoire ne peut en utiliser plus de c'est-à-dire, . Il s’agit du nombre total de configuration possible. Par la même, nous montrons que L est un sous ensemble de P.

Savoir si ce sous ensemble est en réalité une égalité appartient toujours au domaine de la recherche.

· Relations d’inclusions

Finalement, on obtient les relations suivantes :

Ou PSPACE représente la classe des problèmes décidables en espace polynomial et EXPTIME, ceux décidable en temps exponentiel