Décidabilité

Représentation des entrées

Tout ce qu'on construit au sein d'un ordinateur appartient à un ensemble dénombrable. En effet, les programmes sont des mots sur un alphabet fini, ils forment donc un ensemble dénombrable. Les exécutions finies de ces programmes, comprenant alors l'état de la mémoire accédée et modifiée par le programme, forment également un ensemble dénombrable.

Les entrées et les sorties d'un programme sont des valeurs représentables en mémoire, elles forment donc également un ensemble dénombrable.

Cela signifie qu'on peut associer à tout programme et toute donnée, un numéro ou une représentation textuelle unique pour l'identifier.

Dans la suite, on va manipuler des fonctions ou des programmes prenant en entrée d'autres programmes ou données, on pourra considérer ces représentations sous la forme d'une chaine de caractère.

Remarque

On pourrait considérer des entiers, mais en C comme en OCaml, les entiers n'étant pas de précision arbitraire, ils ne peuvent que représenter un ensemble fini de valeurs.

Exemple

On a manipulé l'interprète OCaml, c'est un programme dans lequel on peut taper un texte correspondant à un programme OCaml et qui va répondre par un texte représentant l'évaluation de ce programme. Plus généralement, les compilateurs et les interprètes voient les programmes comme une forme de donnée.

Dans la suite, on identifiera un ensemble à ses représentations pour simplifier les énoncés.

Fonction calculable

Définition

Soient \(E, F\) deux ensembles dénombrables, on dit que \(f : E \rightarrow F\) est calculable s'il existe un programme prenant en entrée \(e \in E\) et renvoyant en temps fini, mais en pouvant accéder à une mémoire infinie, \(f(e)\).

Théorème

L'ensemble des fonctions calculables de \(\N\) dans \(\N\) est dénombrable.

Preuve

Pour chaque fonction calculable \(f\), on choisit un programme \(P_f\) qui la calcule. Deux fonctions distinctes ne peuvent pas être calculées par le même programme, donc \(f \mapsto P_f\) est une injection de l'ensemble des fonctions calculables dans l'ensemble des programmes, qui est dénombrable. Cet ensemble est de plus infini car il contient les fonctions constantes, qui sont calculables. Il est donc dénombrable.

Corollaire

Il existe une infinité non dénombrable de fonctions de \(\N\) dans \(\N\) non calculables.

Preuve

L'ensemble \(\N^\N\) des fonctions de \(\N\) dans \(\N\) n'est pas dénombrable (argument diagonal de Cantor) : si \((f_n)_{n\in\N}\) est une suite de fonctions de \(\N\) dans \(\N\), la fonction \(g : n \mapsto f_n(n) + 1\) diffère de chaque \(f_n\) en \(n\), donc aucune énumération ne contient toutes les fonctions.

Si l'ensemble des fonctions non calculables était au plus dénombrable, \(\N^\N\) serait la réunion de deux ensembles au plus dénombrables, donc serait dénombrable. Absurde.

Machine universelle

Théorème

On considère la fonction qui étant donné un programme \(P\), et une entrée \(e\) pour \(P\) pour laquelle \(P\) renvoie une valeur en temps fini, renvoie le résultat de \(P\) sur \(e\).

Cette fonction est calculable (admis).

On parle alors de programme universel ou de machine universelle dans ce contexte. Dans le contexte de la programmation, on parle plus simplement d'interprète.

On étend naturellement ce programme universel sur des entrées pour lesquelles \(P\) ne termine pas en le faisant lui-même ne pas terminer.

Notons qu'il n'est pas possible que ce programme puisse détecter et renvoyer une valeur spécifique dans les cas où \(P\) ne termine pas. C'est en effet l'objet du paragraphe suivant.

Problème de l'arrêt

Définition

On appelle problème de décision sur \(E\) dénombrable la donnée d'une fonction \(f : E \rightarrow \mathbb{B}\) où \(\mathbb{B} = \{ \top, \bot \}\) est l'ensemble des booléens. Un élément de \(E\) est alors appelé une instance du problème.

On dit alors que le problème consiste à décider la propriété \(f\).

On cherche alors à savoir si le problème est décidable, c'est-à-dire, à savoir si \(f\) est calculable.

Remarque

On peut identifier le problème \(p\) à la donnée de \(E\) et de \(f^{-1}(\{ \top \}) \subset E\), l'ensemble de ses instances positives. Ainsi, on pourra noter \(e \in p \iff e \in f^{-1}(\{ \top \}) \iff f(e) = \top\).

Comme on ne considère que des entrées dénombrables, on peut considérer que \(E = \Sigma^*\) pour \(\Sigma\) un alphabet. On peut alors identifier un problème de décision à la fonction indicatrice d'un langage. On parle ainsi assez souvent de langages à la place de parler de problèmes de décision.

Définition

On appelle problème de l'arrêt le problème qui étant donné un couple \((P,e)\) où \(P\) est un programme et \(e\) une entrée pour celui-ci, décide si \(P\) termine en temps fini sur l'entrée \(e\).

Théorème

Le problème de l'arrêt est indécidable.

Preuve

Par l'absurde, supposons qu'on dispose d'une fonction

val arret : string -> string -> bool

telle que arret p e renvoie true si et seulement si le programme représenté par \(p\) termine sur l'entrée représentée par \(e\).

On définit alors

let bogus p =
    if arret p p
    then let rec f () = f () in 
        f ()
    else 42

Si on note sbogus une représentation textuelle du programme complet contenant arret et bogus, on peut alors demander à évaluer bogus sbogus.

Deux cas :

• bogus sbogus termine, on a alors arret sbogus sbogus qui doit renvoyer true par définition. Mais alors, dans bogus, on rentre dans la branche then qui ne termine pas. Impossible.
• bogus sbogus ne termine pas, on a alors arret sbogus sbogus qui renvoie false et, dans bogus, on passe par le else et la fonction termine. Impossible.

Les deux cas étant impossibles, on en déduit une contradiction.

Il s'agit d'un argument diagonal : on fait agir le programme bogus sur sa propre représentation, de la même manière que Cantor évalue \(f_n\) en \(n\).

Remarque

Pour l'arrêt, le langage associé au problème est l'ensemble des mots \((pr,e)\) où \(pr\) est un programme, \(e\) une entrée et \(pr\) termine sur \(e\).

Remarque

Le problème de l'arrêt est cependant semi-décidable : il existe un programme qui, sur l'entrée \((P, e)\), termine en renvoyant \(\top\) quand \(P\) termine sur \(e\), et ne termine pas sinon. Il suffit en effet d'utiliser la machine universelle pour simuler \(P\) sur \(e\), puis de renvoyer \(\top\). Ce programme ne permet pas de décider l'arrêt car on ne sait jamais, au cours de la simulation, si \(P\) va finir par terminer ou non.

Complexité et problème de décision

Jusqu'ici, on s'est intéressé à la complexité d'un algorithme. Plusieurs algorithmes résolvant un même problème, par exemple le tri de données, pouvant avoir des complexités différentes.

Ici, on va prendre un peu de hauteur et s'intéresser au problème lui-même.

Définition

Définition

On appelle taille d'une instance d'un problème, la taille de sa représentation dans un système de représentation raisonnable, comme la représentation binaire sérialisée de cette donnée.

Remarque

Ici, on est obligé d'être un peu spécifique. En effet, si on ne précise rien de plus pour un entier \(n \in \N\), on pourrait dire qu'il est sa propre représentation, et donc que tout entier est de taille 1, quelle que soit sa grandeur. À l'opposé, on pourrait le représenter en unaire, ce qui obligerait à considérer une taille \(n\), ce qui est inefficace. En passant au binaire, on s'assure une représentation de taille \(\lfloor \log_2 n \rfloor + 1\) pour \(n \ge 1\). Le choix d'une autre base \(b \ge 2\) ne fait que multiplier cette taille par une constante (\(\log_b n = \log_2 n / \log_2 b\)), et ne change donc pas l'ordre de grandeur.

On a déjà vu qu'on définissait la complexité temporelle en pire cas comme étant la suite \((C_n)_{n\in\N}\) où \(C_n\) est le plus grand nombre d'opérations élémentaires sur une entrée de taille \(n\).

Définition

On dit que le problème de décision \(p\) est dans la classe \(\mathbf{P}\) quand il existe un programme décidant \(p\) dont la complexité pour des instances de taille \(n\) est en \(O(f(n))\) avec \(f\) fonction polynomiale en \(n\).

Exemple

On a vu beaucoup de problèmes dans la classe \(\mathbf{P}\) comme l'existence d'un cycle dans un graphe, la détection de palindromes...

Cependant, on sent bien que de nombreux problèmes qu'on a résolus sont polynomiaux, mais comme ce ne sont pas des problèmes de décisions, ils ne sont pas techniquement dans la classe \(\mathbf{P}\).

Réduction polynomiale

Définition

Soient \(p, p'\) deux problèmes de décision sur les entrées respectives \(E\) et \(E'\). Une fonction calculable

\[ f : E \rightarrow E' \]

est appelée une réduction de \(p\) à \(p'\) lorsque

\[ \forall e \in E, e \in p \iff f(e) \in p' \]

Lorsque \(f\) est calculable en temps polynomial, on dit que \(f\) est une réduction polynomiale et on note \(p \le_P p'\).

Théorème

Soit \(f\) une réduction de \(p\) à \(p'\).

• Si \(p'\) est décidable, alors \(p\) est décidable.
• Si \(f\) est une réduction polynomiale et \(p' \in \mathbf{P}\), alors \(p \in \mathbf{P}\).

Preuve

• Si \(D'\) est un programme décidant \(p'\), le programme qui sur l'entrée \(e\) calcule \(f(e)\) puis renvoie \(D'(f(e))\) termine toujours et renvoie \(\top\) si et seulement si \(f(e) \in p'\), c'est-à-dire si et seulement si \(e \in p\).
• Avec le même programme, si \(f\) est calculée en temps \(O(n^k)\) et \(D'\) en temps \(O(n^l)\), alors \(|f(e)| = O(|e|^k)\) car un programme ne peut écrire qu'un nombre borné de symboles par opération élémentaire. Le temps total est donc en \(O(|e|^k + |e|^{kl})\), qui est polynomial.

Remarque

Attention au sens de la réduction : par contraposée, si \(p\) est indécidable et que \(p\) se réduit à \(p'\), alors \(p'\) est indécidable. Pour montrer qu'un nouveau problème \(p'\) est indécidable, on réduit donc un problème connu pour être indécidable (par exemple l'arrêt) vers \(p'\). Réduire \(p'\) vers l'arrêt ne prouve rien : cela montre seulement que \(p'\) n'est pas plus difficile que l'arrêt.

On a vu des passages polynomiaux d'un problème à un autre, mais pas dans le cadre restrictif des problèmes de décision. On peut ainsi citer la réduction de 2-SAT au calcul des composantes fortement connexes.

NP-complétude

Problème NP

Définition

On dit qu'un problème de décision \(p\) sur des entrées \(E\) est dans la classe \(\mathbf{NP}\) lorsqu'il existe une fonction polynomiale \(f\) sur \(\N\) et un problème de décision \(v(p)\) de classe \(\mathbf{P}\) sur \(E \times \mathbb{B}^*\) tel que

\[ \forall e \in E, \quad e \in p \iff \exists c \in \mathbb{B}^*, |c| \le f(|e|) \text{ et } (e,c) \in v(p) \]

On dit que \(v(p)\) est le problème de vérification associé à \(p\).

Ici, on note \(\mathbb{B} = \{ 0, 1\}\) l'ensemble des booléens et \(\mathbb{B}^*\) l'ensemble des mots binaires. Les éléments de \(\mathbb{B}^*\) sont des candidats certificats et lorsque \((e, c) \in v(p)\) on dit que le mot binaire \(c\) est un certificat pour la validité de l'entrée \(e\).

Il s'agit de preuves permettant de vérifier rapidement, à l'aide de son certificat, qu'une instance est positive pour \(p\). Attention, la définition n'est pas symétrique : on ne demande pas de certificat pour les instances négatives.

Remarque

On utilise ici un mot binaire comme certificat et non un ensemble plus spécifique pour que la définition soit valide. Cependant, toute étape de vérification commence par une déserialisation du certificat, c'est-à-dire par la construction d'informations relatives à l'entrée. Si l'entrée est un graphe, un candidat certificat peut être une coloration de ce graphe à l'aide d'un codage des tableaux finis d'entiers. Seuls quelques mots binaires ont alors un sens compatible avec une entrée donnée.

Théorème

\(\mathsf{SAT}\), le problème qui étant donnée une formule du calcul propositionnel décide si elle est satisfiable, est dans la classe \(\mathbf{NP}\).

Preuve

Un certificat pour une formule \(\varphi\) est une valuation de ses variables, codée par un mot binaire de longueur le nombre de variables, donc au plus \(|\varphi|\). Le problème de vérification consiste à évaluer \(\varphi\) pour cette valuation, ce qui se fait en temps polynomial (et même linéaire) en \(|\varphi|\) par un parcours de son arbre syntaxique. Enfin \(\varphi\) est satisfiable si et seulement si un tel certificat existe.

Théorème

\(\mathbf{P} \subset \mathbf{NP}\)

Preuve

Il suffit ici de considérer un certificat factice, par exemple le mot vide pour tout \(e\), et le problème de vérification \(v(p) = \{ (e, c) \mid e \in p \}\), qui est dans \(\mathbf{P}\) car il s'agit juste de décider \(p\) en ignorant \(c\).

Exercice

difficile a-t-on l'inclusion réciproque ?

Note : m'envoyer la preuve pour que je la vérifie avant d'en parler.

Problèmes NP-complets

Définition

Un problème de décision \(p'\) est dit NP-difficile lorsque pour tout problème \(p \in \mathbf{NP}\), on a \(p \le_P p'\).

Il est dit NP-complet lorsqu'il est NP-difficile et dans \(\mathbf{NP}\).

Théorème (Cook-Levin)

\(\mathsf{SAT}\) est NP-complet (admis).

Remarque

• La relation \(\le_P\) est transitive (la composée de deux fonctions calculables en temps polynomial l'est encore, avec le même argument de taille que précédemment). Ainsi, pour montrer qu'un problème \(p' \in \mathbf{NP}\) est NP-complet, il suffit de réduire polynomialement un problème connu pour être NP-complet, comme \(\mathsf{SAT}\), vers \(p'\).
• Si un seul problème NP-complet est dans \(\mathbf{P}\), alors, d'après le théorème sur les réductions, \(\mathbf{P} = \mathbf{NP}\).

Problème d'optimisation et seuil

On considère ici des problèmes d'optimisation : on considère ainsi des entrées \(E\) et des sorties \(S\) avec pour tout \(e \in E\), un ensemble \(V(e) \subset S\). On dispose de plus d'une fonction de coût \(f : S \rightarrow \R\) (ou \(\N\) ou n'importe quel ensemble totalement ordonné) et on cherche pour chaque \(e \in E\) l'élément de \(V(e)\) qui maximise (ou minimise) \(f\).

Exemple

Considérons par exemple le problème MinVertexCover :

• Entrée : un graphe non orienté \(G = (S, A)\).
• Sortie : un sous-ensemble \(V \subset S\) de plus petit cardinal tel que \(\forall a \in A, V \cap a \neq \emptyset\).

Avec la présentation précédente, les entrées sont les graphes non orientés, les sorties sont les ensembles de sommets. Pour un graphe \(G = (S,A)\), on a donc \(V(G) = \{ V \subset S \mid \forall a \in A, V \cap a \neq \emptyset \}\), l'ensemble des couvertures par sommets de \(G\). La fonction de coût est alors juste le cardinal, qu'on cherche à minimiser.

À un tel problème d'optimisation (ici de minimisation), on associe un problème de décision à seuil : étant donnés \(e \in E\) et \(k\), existe-t-il \(v \in V(e)\) tel que \(f(v) \le k\) ? (on remplace par \(f(v) \ge k\) pour un problème de maximisation). Pour MinVertexCover, on obtient le problème VertexCover : étant donnés un graphe \(G\) et un entier \(k\), existe-t-il une couverture par sommets de \(G\) de cardinal au plus \(k\) ?

Si on sait résoudre le problème d'optimisation, on sait résoudre le problème à seuil associé ; le problème à seuil est donc au plus aussi difficile que le problème d'optimisation.