Deux exemples pour rentrer dans le sujet :
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.
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.