III. Complexité

Introduction

Deux exemples pour rentrer dans le sujet :

  • Problème du voyageur de commerce. Etant donné une carte routière et une liste de N villes, comment réaliser un circuit qui visite les N villes en parcourant la plus courte distance possible.
  • Géométrie tortue : void triangle(float x, float y, float d, float h){ if (y+d)<h {tracer(x-d, y+d); triangle(x-d, y+d, d, h); tracer(x+d, y+d); triangle(x+d, y+d, d, h); tracer(x,y);}} .
    complexité ~ sk avec y+kd < h < y+(k+1)d.

La classe P

Définition : bornitude polynomiale

Une machine de Turing M\left(K, \Sigma, \delta, s, H\right) est dite bornée polynialement (en temps) si et seulement si il existe un polynôme P tel que pour tout mot w\in \Sigma^* M s'arrête avec w en entrée en au plus P(|w|) étapes.

La classe des langages (récursifs) décidés par une MT polynomialement bornée s'appelle la classe P.

Théorème

La classe P est stable par complément.

Preuve

Inverser Y et N, évidement.

Théorème

Il existe des langages récursifs qui ne sont pas dans P.

Preuve

Exemples et Problèmes

SAT

la classe NP

“NP” = non-déterministe polynômiale

Définition

Une MT non-déterministe est bornée polynomialement si et seulement si il existe P (polynôme) tel que pour w\in \Sigma^* M s'arrête avec w en entrée en moins de P(|w|) étapes quelque soit le calcul suivi. Autrement dit, il n'existe pas de configuration C avec
\left(s, \triangleright \underline{\sqcup} w\right) \vdash_{M}^{P\left(|w|\right)+1} C

On appelle NP la classe des langages décidés par te telles machines.

Proposition

SAT est dans NP.

Preuve

Machine à 2 rubans. F (la formule) est sur le premier ruban, n –un entier en binaire–est sur le deuxième ruban; n a un bit pour chaque variable de F.

  • 1. chercher le nombre de variables dans F.
  • 2. Ecrire un nombre en binaire, pris entre 0 et 2^n - 1 de manière non-déterministe, sur le deuxième ruban.
  • 3. Interpreter F en fonction de ce nombre, prenant le bit le plus à gauche pour la variable 1, son voisin droit pour variable 2, et ainsi de suite.

F est satisfiable si l'une des évaluations donne vraie.

Propriété

\mathcal{P} \subseteq \mathcal{NP}

Preuve

Une MT est une instance particulière d'une MT non-déterministe.

Est-ce que \mathcal{NP} \subseteq \mathcal{P} : on ne sait pas.

Définition

Une MT (M) est dite exponentiellement bornée si et seulement si \exists P tel que \forall w \in \Sigma^* la machine s'arrête avec w en entrée en au plus 2^{P(|w|)} étapes. On note <jsm>\mathcal{EXP} la classe des langages décidés par de telles machines.

Proposition

\mathcal{P} \subseteq \mathcal{NP} \subseteq \mathcal{EXP}

Preuve

Provient de l'algorithme de détermination d'un MT non-déterministe.

NP-complétude


Navigation


 
m1ilc/c_et_c_d.txt · Dernière modification: 2010/01/06 14:43 par suitable