Décidabilité – Classe – Complexite

Problème de décision

Un problème de décision est un problème, portant sur un domaine d'entrées, et dont la réponse est « oui » ou « non ».

Une instance d'un problème de décision est représentée par une entrée donnée, avec sa solution attendue qui est une valeur booléenne.

Fonction calculable

Une fonction calculable $f$ est une fonction qui peut être implémentée par un algorithme. On dit que l'algorithme permet de calculer la fonction, ce qui implique pour toute valeur du domaine d'entrées $x$, l'algorithme produit un résultat y (« oui » ou « non ») tel que $y = f(x)$.

Un problème de décision peut être résolu si l'on peut construire un algorithme (et donc une fonction calculable) qui pour toute instance du problème en entrée produit le résultat attendu.

Illustration

Exemples de problèmes de décision

Problème de satisfiabilité SAT : Étant donnée une formule booléenne, existe-t-il une affectation des variables qui rend la formule vraie ?

Problème de la clique : Étant donné un graphe et un entier k, existe-t-il une clique de taille au moins k dans le graphe ?

Contre-exemples

Problème du voyageur de commerce : Étant donné un ensemble de villes et les distances entre elles, trouver le plus court chemin visitant chaque ville exactement une fois. Ici, la réponse attendue est une route optimale et non une réponse booléenne.

Multiplication de deux entiers : Étant donné deux nombres entiers, le problème consiste à calculer leur produit. La réponse attendue est un nombre et non un simple « oui » ou « non ».

Transformation d'un problème d'optimisation en problème de décision

Un problème d'optimisation peut être converti en problème de décision en introduisant un seuil.

Exemple : Problème du voyageur de commerce

• Problème d'optimisation : Trouver le plus court chemin visitant chaque ville exactement une fois.
• Transformation en problème de décision : Étant donné un entier k, existe-t-il un chemin pour traverser toutes les villes dont la longueur est inférieure ou égale à k ?

Problèmes décidables et indécidables

Un problème de décision est dit décidable s'il existe un algorithme qui résout toute instance de ce problème en un nombre fini d'étapes. Dans ce cas, l'algorithme renverra « oui » si $f(x) = oui$ et « non » si $f(x) = non$.

Un problème est indécidable s'il n'existe aucun algorithme permettant de répondre correctement à toutes les instances du problème en un nombre fini d'étapes.

Problèmes semi-décidables

Un problème de décision est dit semi-décidable s'il existe un algorithme qui peut répondre « oui » lorsque $f(x) = oui$. En revanche, il peut ne jamais s'arrêter, ou échouer, lorsque $f(x) = non$. Autrement dit, il existe un algorithme qui accepte toutes les instances pour lesquelles la réponse est « oui », mais il peut ne pas toujours donner de réponse pour les instances où la réponse est « non ».

Le problème de l'arrêt

Le problème de l'arrêt est le problème de décision suivant : Étant donné un programme informatique $P$ et une entrée $x$, peut-on déterminer de manière générale si $P$ va s'arrêter ou tourner indéfiniment lorsqu'il est exécuté avec $x$ ?

Autrement dit, existe-t-il une méthode systématique qui, pour n'importe quel programme et n'importe quelle entrée, garantit de répondre correctement par « oui » (le programme s'arrête) ou « non » (le programme tourne indéfiniment) ?

Indécidabilité

Le problème de l'arrêt est indécidable. Aucun algorithme universel ne peut y répondre correctement dans tous les cas.

La preuve de cette indécidabilité repose sur un raisonnement par contradiction où l'on suppose qu'un programme $H(P, x)$ existe et décide correctement si un programme $P$ s'arrête sur une entrée $x$.

On pose ensuite un programme $D(P)$ qui :

• Appelle $H(P, P)$ pour vérifier si $P(P)$ s'arrête ;
• Si $H(P, P)$ dit « oui », alors $D$ boucle infiniment ;
• Si $H(P, P)$ dit « non », alors $D$ s'arrête immédiatement.

On obtient alors une contradiction avec $D(D)$ :

• Si $H(D, D)$ dit « oui », alors $D(D)$ boucle infiniment, contradiction ;
• Si $H(D, D)$ dit « non », alors $D(D)$ s'arrête, contradiction.

Comme ces deux cas sont impossibles, $H$ ne peut pas exister.

Semi-décidabilité

Bien que le problème de l'arrêt soit indécidable, il est aussi semi-décidable, ce qui signifie qu'il est possible de détecter les cas où la réponse est « oui », mais pas toujours les cas où la réponse est « non ».

En effet, si $P(x)$ s'arrête, il suffit d'exécuter $P(x)$ et d'attendre : on finit par obtenir la réponse « oui ». En revanche, si $P(x)$ tourne indéfiniment, il est impossible de prouver en un temps fini qu'il ne s'arrêtera jamais. Cela signifie que le problème est semi-décidable : on peut détecter les cas « oui », mais pas toujours les cas « non ».

Problèmes P et réduction polynomiale

Taille d'une instance et complexité temporelle

La taille d'une instance d'un problème est la quantité de mémoire nécessaire pour la représenter.

La complexité en temps d'un algorithme est le nombre d'opérations élémentaires effectuées en fonction de la taille de l'instance. Une opération élémentaire est une opération de base dont le temps d'exécution est considéré comme constant, comme une addition ou une comparaison.

Exemple : L'algorithme de tri par insertion a une complexité $O(n^2)$.

Problèmes P

La classe P regroupe les problèmes de décision qui peuvent être résolus par un algorithme déterministe en temps polynomial. Autrement dit, un problème appartient à P s'il existe un algorithme qui, avec une instance de taille n, le résout en un temps $O(n^k)$ pour un entier k.

Exemple de problème en P : Le tri d'une liste (car il existe des algorithmes de tri en $O(n \log n)$).

Réduction polynomiale

Un problème A se réduit polynomialement à un problème B si toute instance de A peut être transformée en une instance de B en temps polynomial.

Exemples

Problème de la clique → problème SAT : Un graphe contient une clique de taille k si est seulement si une formule SAT particulière est satisfiable.

Voyageur de commerce (décision) → problème du chemin hamiltonien : Vérifier s'il existe un chemin de coût ≤ k peut être transformé en un problème de chemin hamiltonien pondéré.

Coloration de graphe → problème SAT : Savoir si un graphe est k-colorable peut être transformé en une formule SAT.

Problèmes NP et machine de Turing

Problèmes NP

La classe NP regroupe les problèmes pour lesquels une solution candidate peut être vérifiée en temps polynomial.

Un problème P appartient à NP si, une fois une solution fournie, on peut la vérifier en temps polynomial.

$P \subseteq NP$, mais on ne sait pas si $P = NP$.

Problèmes NP-difficiles et NP-complets

Un problème est NP-difficile s'il est au moins aussi difficile que tous les problèmes de NP (même s'il n'est pas forcément un problème de décision).

Un problème est NP-complet s'il est dans NP et NP-difficile.

Exemples de problèmes NP-complets

• Problème SAT
• Problème de la clique
• Problème du voyageur de commerce (version décision, avec seuil)

Théorème de Cook-Levin et NP-complétude de SAT

Le théorème de Cook-Levin montre que SAT est NP-complet.

Une fois un problème NP-complet identifié, on peut montrer que d'autres problèmes sont NP-complets par réduction polynomiale.

Exemples

• Problème SAT → Problème 3SAT
• Problème 3SAT → Problème de la clique
• Problème de la clique → Couverture de sommets

Machine de Turing universelle

Une machine de Turing est un modèle abstrait de calcul qui manipule des symboles sur un ruban infini, en suivant un ensemble de règles définies dans une table de transition. Elle formalise la notion d'algorithme et permet de modéliser tout système de calcul réalisable par un ordinateur.

Une machine de Turing universelle est une machine capable de simuler n'importe quelle autre machine de Turing en prenant en entrée sa description et ses données. Ce concept est fondamental en informatique théorique, car il établit la possibilité de concevoir des machines programmables exécutant n'importe quel algorithme.

Une machine de Turing universelle peut être utilisée pour vérifier si un problème de décision est résoluble par un algorithme. Ainsi, elle permet de classer les problèmes en décidables, semi-décidables et indécidables, jouant un rôle central dans l'étude de la calculabilité et de la complexité.