Problèmes et algorithmes de décision

On définit la classe de problèmes NP comme étant ceux permettant de vérifier efficacement leurs solutions. Cette approche, pratique, permet de comprendre l'utilité de cette classe, mais n'est pas très opérationnelle pour faire des démonstrations.

Nous allons dans cette partie redéfinir la notion de problème algorithmique via les problèmes de décision.

Décision et algorithmes

Rappelons qu'un algorithme est dans toute sa généralité une fonction qui prend et rend un mot de $\{0, 1\}$. On peut lui associer de façon équivalente la fonction $v_f : \{0, 1\}^\star \times \{0, 1\}^\star \rightarrow \{0, 1\}$ ci-dessous :

$$ v_f(n, m) = \left\{ \begin{array}{ll} 1 & \mbox{si } f(n) = m\\ 0 & \mbox{sinon.} \end{array} \right. $$

Un algorithme est ainsi un vérifieur. Nous allons monter dans cette partie une version équivalente, plus simple à manipuler théoriquement, mais moins opérationnelle en pratique d'un algorithme.

Décideur et algorithmes

On peut combiner les deux mots en entrée d'un vérifieur en un seul pour arriver à la formulation d'un algorithme qui nous intéressera ici. Pour cela, la façon classique de procéder est de coder chaque information (0 et 1) sur 2 bits ce qui permet d'avoir un caractère supplémentaire de séparation :

• on code l'information 0 en 00
• on code l'information 1 en 01
• 11 est le caractère de séparation des paramètres

Ainsi, si un algorithme possède 2 paramètres valant 1001, 001 par exemple, cela devient le paramètre 0100000111000001. on modifie alors l'algorithme pour que la première chose qu'il fasse soit de retrouver les deux paramètres en entrée :

1. on trouve les paramètres en découpant la chaîne d'entrée aux endroits où se trouvent le séparateur 11
2. on reconvertit chaque caractère en binaire en ne prenant qu'un bit sur 2

Au final on obtient qu'un algorithme est équivalent à un décideur :

On peut représenter un algorithme sous 3 formes équivalentes :

• une fonction : $f: \{0, 1\}^\star \rightarrow \{0, 1 \}^\star$ qui permettent le calcul effectif,
• un décideur : $d: \{0, 1\}^\star \rightarrow \{0, 1 \}$ qui permettent de séparer les mots en 2 ensembles, ceux qui sont vrais pour $A$ : $\{ x \vert A(x) = 1 \}$ et les autres
• un vérifieur : $v: \{0, 1\}^\star \times \{0, 1\}^\star \rightarrow \{0, 1\}$ qui, associé à un problème algorithmique $P$, permettent de vérifier si le couple $(x, y)$ en entrée est tel que $y$ soit une solution de $P$ avec $x$ comme entrée.

TBD un même problème peut se voir sous sa forme fonction, vérifieur ou décideur. TBD : exemple du Max tableau et de ? un élément strictement plus grand que K.

Langages et Turing

Si on veut appliquer la notion de décideur à une machine de Turing, cela revient à ne considérer que la case du ruban sous le curseur lorsque la machine s'arrête. On dira alors :

TBD exemple avec accepte, rejette et infini.

On peut alors chercher à connaître toutes les entrées acceptées par une machine :

Remarquez que dans la définition précédente, décider un langage est bien plus fort qu'uniquement reconnaître un langage puisque la machine ne bouclera jamais indéfiniment.

TBD reprendre exemple précédent. Puis transformer M pour qu'elle décide.

Enfin, l'algorithmie peut être vu comme la reconnaissance des ensembles pouvant être un langage reconnaissable ou, mieux encore, décidable.

TBD exemple de langages reconnaissable et décidable.

Décideur et Langage

En conclusion, en utilisant les machines de Turing, on définit les problèmes algorithmiques comme étant des problèmes de décision associé à un langage décidable :

Algorithme, décision et langages sont donc trois notions équivalentes : un algorithme est caractérisé par l'ensembles des mots qu'il décide.

Complexités des problèmes de décision

La complexité d'un problème est la complexité la plus petite d'une machine de Turing qui le résout. Comme résoudre un problème de décision revient à trouver un décideur pour son langage on a :

Comme une machine de Turing prend en entrée un mot de $\{0, 1\}^\star$, sa complexité sera forcément calculé par rapport à sa taille. Pour une machine de Turing $M$ prenant une entrée $E$ en paramètre, on notera dans cette partie :

• $C(\vert E \vert)$ sa complexité.
• $S(\vert E \vert)$ sa complexité spatiale,

On sait que la complexité spatiale d'une machine de Turing est forcément plus petite que sa complexité temporelle, mais la proposition suivante va plus loin et propose un encadrement :

P, NP et décision

On peut maintenant redéfinir les classes $P$ et $NP$ grace aux langages. Commençons par la classe $P$ :

Pour définir précisément ce qu'est la classe NP en revanche, il faut introduire un autre modèle de Machine de Turing, les machines non déterministes :

On a alors :

La classe de problème $NP$ a été précédemment construite via l'existence d'un vérifieur polynomial qui vérifie si la solution est correcte ou pas. Avec cette nouvelle définition, le certificat est la suite de choix effectués par la machine de Turing non déterministe. Voyez ces choix comme un oracle (ou un prof) qui vous guide tout au long du déroulement de la machine. On peut s'en passer mais cela prendrait beaucoup de temps (faire tout les choix amène à une complexité exponentielle). Si on sait déjà ou aller en revanche, on peut trouver rapidement une solution (en temps polynomiale).

Cas du NON

SAT est NP-complet

On verra qu'il y en a beaucoup, beaucoup d'autres.

Hiérarchie des complexités

Terminons cette partie en montrant qu'il existe bien d'autres algorithmes que ceux de NP. On peut même trouver des problèmes de toute complexité.