Décidabilité et classes de complexité

Cours complet · informatique (MP2I/MPI), chapitre 31 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

31.1 Ce qu'un algorithme ne peut pas faire

Ce dernier chapitre change de question. Les trente précédents demandaient comment résoudre un problème ; celui-ci demande si l'on peut, et à quel prix. Le programme le formule ainsi : « on s'intéresse à la question de savoir ce qu'un algorithme peut ou ne peut pas faire, inconditionnellement ou sous condition de ressources en temps. Cette partie permet de justifier la construction, plus haut, d'algorithmes exhaustifs, approchés, probabilistes. »

C'est donc le chapitre qui explique a posteriori pourquoi le chapitre chap:probabilistes existe.

AttentionLe modèle de calcul, et ce que le programme en écarte

« La notion de machine de Turing est hors programme. On s'en tient à une présentation intuitive du modèle de calcul (code exécuté avec une machine à mémoire infinie). » Et plus loin : « le modèle de calcul est une machine à mémoire infinie qui exécute un programme rédigé en OCaml ou en C ». Enfin : « les modèles de calcul non-déterministes sont hors programme ».

On raisonne donc sur des programmes ordinaires, avec une mémoire idéalement illimitée. C'est suffisant pour tout ce qui suit.

31.2 Mesurer

Définition 31.1Problème de décision, taille d'une instance

Un problème de décision appelle une réponse par oui ou non. Une instance est une donnée particulière, et sa taille est le nombre de bits nécessaires pour l'écrire.

ImportantLa taille se compte en BITS, et c'est le piège du chapitre

Le chapitre chap:dynamique l'annonçait : l'algorithme du sac à dos en $Θ (n C)$ n'est pas polynomial, car $C$ s'écrit avec $lo g_{2} C$ bits. Un algorithme dont le coût est proportionnel à la valeur d'un nombre est exponentiel en sa taille.

Entrée	Taille	Coût de $Θ (C)$
$C = 1000$	$10$ bits	$1 0^{3}$
$C = 1 0^{9}$	$30$ bits	$1 0^{9}$
$C = 1 0^{18}$	$60$ bits	$1 0^{18}$

Trois fois plus de bits — de $10$ à $30$ — et un million de fois plus de travail ; six fois plus, et c'est $1 0^{15}$ . C'est bien une exponentielle, et il suffit de lire le tableau ligne à ligne pour s'en convaincre. On dit l'algorithme pseudo-polynomial.

Définition 31.2Opération élémentaire, complexité en temps

Une opération élémentaire est une lecture ou écriture en mémoire, une opération arithmétique, une comparaison — chacune comptée pour une unité. La complexité en temps d'un algorithme est le nombre d'opérations élémentaires en fonction de la taille de l'entrée, dans le pire cas.

31.3 Les classes P et NP

Définition 31.3La classe P

$P$ est l'ensemble des problèmes de décision pour lesquels il existe un algorithme de complexité polynomiale en la taille de l'entrée.

Important« Classe de complexité d'un problème » n'est pas « complexité d'un algorithme »

Le programme y insiste : « on prend soin de distinguer la notion de complexité d'un algorithme de la notion de classe de complexité d'un problème ».

Complexité d'un algorithme	ce que cet algorithme coûte
Classe d'un problème	ce que coûte le meilleur algorithme, connu ou non

Le second énoncé est infiniment plus fort. Dire « le tri est en $O (n lo g n)$ » parle d'un algorithme ; dire « ce problème n'est pas dans $P$ » affirmerait que personne, jamais, n'en trouvera de polynomial. C'est pourquoi les résultats de la seconde espèce sont si rares.

Et $P$ ne contient que des problèmes de décision — le programme le souligne. « Trouver le plus court chemin » n'est pas dans $P$ à proprement parler ; « existe-t-il un chemin de longueur $\leq k$ ? » y est.

Définition 31.4Transformation d'une optimisation en décision

Le programme demande cette « transformation d'un problème d'optimisation en un problème de décision à l'aide d'un seuil ». On remplace « quel est le minimum ? » par « existe-t-il une solution de coût $\leq k$ ? ».

Les deux versions sont équivalentes en difficulté : par dichotomie sur $k$ — celle du chapitre chap:diviser — un nombre logarithmique d'appels à la version décision donne la valeur optimale.

Définition 31.5Certificat, classe NP

$NP$ est l'ensemble des problèmes de décision dont toute réponse « oui » admet un certificat de taille polynomiale, vérifiable en temps polynomial.

ImportantNP se lit « vérifiable vite », et non « résoluble vite »

C'est le point le plus mal compris de la théorie. $NP$ n'est pas « non polynomial ». Le programme donne d'ailleurs la définition par la vérification, et écarte les modèles non déterministes.

Problème	Certificat	Vérification
sat	une valuation	évaluer la formule : $O (∣ φ ∣)$
$k$ -coloration	une coloration	vérifier chaque arête : $O (m)$
Sac à dos ( $\geq k$ ?)	la liste des objets	sommer poids et valeurs : $O (n)$
Chemin hamiltonien	l'ordre des sommets	vérifier les arcs : $O (n)$

Dans les quatre cas, trouver le certificat semble exiger une recherche exponentielle ; le vérifier prend quelques lignes.

Proposition 31.6

P \subseteq NP

Démonstration

Si un problème se résout en temps polynomial, le certificat peut être vide : le vérificateur ignore le certificat et relance l'algorithme de résolution, qui est polynomial.

ImportantLa question

P = NP

L'inclusion réciproque est ouverte depuis 1971. Personne n'a exhibé d'algorithme polynomial pour un problème np-complet, et personne n'a démontré qu'il n'en existe pas.

Ce qu'il faut en retenir n'est pas une opinion sur la réponse, mais sa conséquence pratique : sur un problème np-complet, on ne cherche pas d'algorithme exact et rapide — on emploie les méthodes du chapitre chap:probabilistes.

31.4 Réductions et NP-complétude

Définition 31.7Réduction polynomiale

Un problème $A$ se réduit polynomialement à $B$ , noté $A \leq_{p} B$ , s'il existe une fonction $f$ calculable en temps polynomial telle que

$x est une instance positive de A ⟺ f (x) est une instance positive de B .$

Le programme s'en tient « à quelques exemples élémentaires ».

ImportantLire une réduction dans le bon sens

$A \leq_{p} B$ signifie : $B$ est au moins aussi difficile que $A$ . Car si l'on savait résoudre $B$ vite, on résoudrait $A$ vite — en traduisant puis en résolvant.

C'est le sens que l'on inverse une fois sur deux. La mnémonique : la réduction transporte la difficulté vers la cible. On réduit un problème connu difficile vers celui qu'on étudie, pour montrer que le nouveau est difficile aussi.

Définition 31.8NP-difficile, NP-complet

Un problème $B$ est np-difficile si tout problème de $NP$ s'y réduit polynomialement. Il est np-complet s'il est de plus dans $NP$ .

Les problèmes np-complets sont donc les plus difficiles de $NP$ : si l'un d'eux était dans $P$ , tous y seraient, et $P = NP$ .

◆Théorème 31.9Cook-Levin, admis

sat est np-complet.

ImportantPourquoi ce théorème est le pivot de tout

Le programme l'admet — « théorème de Cook-Levin (admis) » — et demande d'en tirer des réductions : « on présente des exemples de réduction de problèmes np-complets à partir de sat ».

Sa portée : il fournit le premier problème np-complet, celui à partir duquel tous les autres se démontrent. Une fois sat établi, montrer qu'un problème $B$ est np-difficile ne demande plus qu'une réduction $s a t \leq_{p} B$ — un travail fini, souvent élégant, au lieu d'un raisonnement sur tous les problèmes de $NP$ .

Le programme ajoute une limite : « la connaissance d'un catalogue de problèmes np-complets n'est pas un objectif du programme ». On retient la méthode, pas la liste.

Exemple 31.10Une réduction :

3

-sat

\leq_{p}

coloration

On construit, à partir d'une formule $φ$ en $3$ -fnc, un graphe $3$ -coloriable si et seulement si $φ$ est satisfiable. Trois couleurs : V, F, N (neutre).

Le socle : un triangle sur trois sommets $v, f, n$ — ils reçoivent forcément trois couleurs distinctes, qui nomment les couleurs.

Les variables : pour chaque $x$ , deux sommets $x$ et $x ˉ$ reliés entre eux et tous deux reliés à $n$ . Ils reçoivent donc l'un V et l'autre F : la coloration est une valuation.

Les clauses : un petit assemblage par clause, construit pour être $3$ -coloriable exactement lorsqu'au moins un de ses trois littéraux reçoit V.

La construction est polynomiale — un nombre borné de sommets par variable et par clause — et l'équivalence est immédiate par construction. Donc la $3$ -coloration est np-difficile.

Bonne pratique (Ce qu'on fait quand un problème est NP-complet)

C'est la conclusion utile, et elle rassemble le livre.

Si l'instance est petite	exhaustif ou branch and bound (ch. chap:exploration, chap:probabilistes)
Si un paramètre reste petit	programmation dynamique pseudo-poly. (ch. chap:dynamique)
Si l'à-peu-près suffit	approximation garantie (ch. chap:gloutons)
Si l'on accepte un risque	algorithme probabiliste (ch. chap:probabilistes)
Si le cas particulier s'y prête	$2$ -sat est linéaire (ch. chap:graphes-avances)

La dernière ligne mérite attention : np-complet qualifie le problème général. Un cas particulier peut être facile, et c'est souvent là qu'est la solution réelle.

31.5 L'indécidable

Jusqu'ici, la difficulté était une question de temps. Il existe pire.

Définition 31.11Machine universelle

Un programme peut prendre un autre programme en donnée. Une machine universelle est un programme $U$ qui, recevant le texte d'un programme $p$ et une entrée $x$ , simule l'exécution de $p$ sur $x$ .

Ce n'est pas une abstraction : tout interpréteur en est une, et le chargeur du système d'exploitation aussi.

Définition 31.12Problème de l'arrêt

arrêt : étant donné le texte d'un programme $p$ et une entrée $x$ , l'exécution de $p$ sur $x$ se termine-t-elle ?

◆Théorème 31.13Indécidabilité de l'arrêt

Aucun programme ne décide arrêt pour toutes les entrées.

Démonstration

Supposons qu'existe un programme arrete : string -> string -> bool qui rende true exactement quand le programme de texte $p$ termine sur l'entrée $x$ . Construisons alors :


(* d prend le TEXTE d'un programme, et fait le contraire de ce qu'il fait. *)
let d p =
  if arrete p p then boucle_infinie ()      (* il s'arrête -> on boucle *)
  else ()                                   (* il boucle   -> on s'arrête *)

Soit $δ$ le texte de d, et appliquons d à $δ$ .

Si d $δ$ termine, alors arrete $δ$ $δ$ a rendu false — donc, par correction de arrete, d $δ$ ne termine pas.
Si d $δ$ ne termine pas, alors arrete $δ$ $δ$ a rendu true — donc d $δ$ termine.

Les deux cas se contredisent. arrete ne peut donc pas exister.

ImportantCe que l'indécidabilité veut dire, et ce qu'elle ne veut pas dire

Ce que le théorème dit	Ce qu'il ne dit pas
aucun programme ne répond pour toutes les entrées	qu'on ne puisse répondre sur certains programmes
aucune amélioration de matériel n'y changera rien	que l'analyse statique soit inutile
c'est une limite logique, pas technique	que les outils réels ne servent à rien

La colonne de droite est celle qu'on oublie. Les analyseurs de programmes existent et sont utiles : ils répondent « termine », « ne termine pas », ou « je ne sais pas ». C'est cette troisième réponse qui rend la chose possible, et c'est aussi pourquoi un compilateur vous avertit sans jamais garantir l'absence de bogue.

iRemarqueDeux niveaux de difficulté, à ne pas confondre

	Un algorithme existe ?	Est-il rapide ?
$P$	oui	oui, polynomial
np-complet	oui (l'exhaustif)	personne n'en connaît de rapide
Indécidable	non, et c'est démontré	sans objet

La deuxième ligne est une ignorance — peut-être temporaire. La troisième est un théorème : aucun progrès ne la lèvera.

31.6 Ce qu'il faut retenir

ImportantLe dernier chapitre, en six points

La taille d'une instance se compte en bits. $Θ (n C)$ est pseudo-polynomial, donc exponentiel.
La classe d'un problème n'est pas la complexité d'un algorithme : la première parle de tous les algorithmes, connus et inconnus.
$NP$ signifie « certificat vérifiable en temps polynomial », jamais « non polynomial ».
$A \leq_{p} B$ veut dire $B$ est au moins aussi difficile que $A$ . sat est np-complet (Cook-Levin, admis), et sert de point de départ à toutes les autres réductions.
Un problème np-complet n'interdit pas d'agir : exhaustif borné, pseudo-polynomial, approximation garantie, probabiliste, ou cas particulier facile.
Le problème de l'arrêt est indécidable — non par manque de puissance, mais par contradiction logique. C'est une limite définitive, et elle laisse place aux outils qui répondent « je ne sais pas ».

Continuer sur Adloun : animation, QCM, fiches, exercices