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é ~ s^k avec y+kd < h < y+(k+1)d.

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.

La classe P est stable par complément.

Inverser Y et N, évidement.

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

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

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.

SAT est dans NP.

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.

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

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.

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.

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

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

II.5 Problèmes indécidables pour les grammaires