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

==== La classe P ====

=== Définition : bornitude polynomiale ===

> Une machine de Turing <jsm>M\left(K, \Sigma, \delta, s, H\right)</jsm> est dite bornée __polynialement__ (en temps) si et seulement si il existe un polynôme P tel que pour tout mot <jsm>w\in \Sigma^*</jsm> 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 <jsm>w\in \Sigma^*</jsm> 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 <jsmath> \left(s, \triangleright \underline{\sqcup} w\right) \vdash_{M}^{P\left(|w|\right)+1} C </jsmath>

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 <jsm>2^n - 1</jsm> 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é ===

<jsm>\mathcal{P} \subseteq \mathcal{NP}</jsm>

== Preuve ==

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

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

=== Définition ===

Une MT (M) est dite __exponentiellement bornée__ //si et seulement si// <jsm>\exists P </jsm> tel que <jsm>\forall w \in \Sigma^*</jsm> la machine s'arrête avec w en entrée en au plus <jsm>2^{P(|w|)} étapes.

On note <jsm>\mathcal{EXP}</jsm> la classe des langages décidés par de telles machines.

=== Proposition ===

<jsm>\mathcal{P} \subseteq \mathcal{NP} \subseteq \mathcal{EXP} </jsm>

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


==== NP-complétude ====


----
==== Navigation ====

[[c_et_c_b| ]]