Décidabilité et classes de complexité
Cours · informatique (MP2I/MPI), chapitre 31 · MP2I et MPI · le début du chapitre, la suite sur Adloun
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.
« 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
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.
Le chapitre chap:dynamique l'annonçait : l'algorithme du sac à dos en n'est pas polynomial, car s'écrit avec 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 |
|---|---|---|
| bits | ||
| bits | ||
| bits |
Trois fois plus de bits — de à — et un million de fois plus de travail ; six fois plus, et c'est . C'est bien une exponentielle, et il suffit de lire le tableau ligne à ligne pour s'en convaincre. On dit l'algorithme pseudo-polynomial.
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
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.
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 » parle d'un algorithme ; dire « ce problème n'est pas dans » affirmerait que personne, jamais, n'en trouvera de polynomial. C'est pourquoi les résultats de la seconde espèce sont si rares.
Et ne contient que des problèmes de décision — le programme le souligne. « Trouver le plus court chemin » n'est pas dans à proprement parler ; « existe-t-il un chemin de longueur ? » y est.
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 ? ».
Les deux versions sont équivalentes en difficulté : par dichotomie sur — celle du chapitre chap:diviser — un nombre logarithmique d'appels à la version décision donne la valeur optimale.
Exercices du chapitre
- Le test de primalité naïf est-il polynomial ? corrigé
- Le certificat vide corrigé
- Du seuil à l'optimum corrigé
- Lire une réduction dans le bon sens corrigé
- Deux problèmes, une réduction d'une ligne corrigé
- L'arrêt sur l'entrée vide corrigé