Si l’on revient à la définition de la complexité d’un algorithme, c’est donc au final un “minimun d’un maximum”. Minimum pour tous les algorithmes qui répondent au problème. Maximum pour toutes les entrées possibles de taille donnée.
Classes de complexité
Il existe des problèmes plus difficiles que d’autres, en cela qu’ils nécessitent des algorithmes plus complexes pour être résolus.
Par exemple, un problème est dit polynomial s’il existe un algorithme y répondant dont la complexité est asymptotiquement dominée par un polynôme.
Dans le cours, nous avons rencontré déjà pas mal d’algorithmes polynomiaux : les parcours, Dijkstra et Floyd-Warshall en sont des exemples. Il est dans ces cas facile de montrer qu’un problème est polynomial car il suffit de trouver un algorithme polynomial qui les résout. Ces problèmes sont dits de classe P (pour Polynomial).
Pour d’autres problèmes c’est plus difficile. Le voyageur de commerce vu en cours en est un exemple. À ce jour personne n’a trouvé d’algorithme polynomial pour le résoudre, et il y a même de fortes suspicions que cela n’est pas possible.
Le problème du voyageur de commerce appartient à une classe de problèmes plus difficiles, appelés problèmes NP (pour “Nondeterministic Polynomial”). Les problèmes NP sont délicats à présenter formellement, car ils nécessitent des notions d’informatique fondamentale complexes. Globalement leur complexité est souvent exponentielle. Toutefois, les problèmes P sont aussi inclus dans les problèmes NP.
Une classe particulièrement célèbre de problèmes est celle des NP-Complets. Les problèmes NP-Complets, comme celui du voyageur de commerce, sont au moins aussi difficiles que tous les autres problèmes NP. Autrement dit, un algorithme pouvant résoudre un problème NP-Complet peut résoudre tout autre problème NP, il suffit pour cela de réécrire l’entrée et de réinterpréter la sortie pour l’adapter au nouveau problème. Ces réécritures peuvent être faites par des algorithmes polynomiaux.
Ainsi, théoriquement lorsque vous aurez terminé votre travail sur le voyageur de commerce, vous serez capables de résoudre tous les problèmes NP. Et il y a de fortes chances pour que vous ne tombiez jamais sur des problèmes plus difficiles.
Réduction
En informatique, on appelle réduction d’un problème p à un problème q le fait de trouver deux algorithmes polynomiaux alg1 et alg2 tels que : si un algorithme alg résout le problème q, alors l’algorithme concaténé [alg1, alg, alg2] résout le problème p.
C’est une façon très pratique de prouver des résultats rapidement, comme par exemple le fait qu’un problème peut être résolu par un algorithme, ou encore qu’il est dans une classe de complexité donnée. En effet si q est dans P alors p aussi et si q est dans NP alors p aussi.
Quelques autres exemples de problèmes NP-Complets célèbres
3-SAT
Le problème 3-SAT consiste à trouver pour une formule de logique ayant une forme particulière s’il existe une instanciation des variables qui la rende vraie. La forme particulière est qu’il s’agit d’une conjonction (un “ET”) de disjonctions (des “OU”) de 3 éléments à chaque fois (d’où le 3 dans 3SAT), chaque élément étant soit une variable soit le contraire d’une variable.
On remarque qu’une solution algorithmique évidente consiste à tester toutes les possibilités pour les valeurs des variables, nombre qui croît exponentiellement avec le nombre de variables.
Problème du sac à dos
Le problème du sac à dos consiste à choisir parmi une liste d’objets ayant chacun un poids et une valeur monétaire, une liste d’objets ne dépassant pas un poids limite et de valeur monétaire maximale.
Une solution évidente consiste à énumérer tous les ensembles d’objets possibles et à retenir celui qui satisfait la contrainte de valeur maximale. Il y a autant de possibilités que de parties de l’ensemble des objets, donc un nombre exponentiel.
Le problème de la clique
Une clique dans un graphe est un ensemble de sommets tous connectés les uns aux autres. Trouver si un graphe donné contient une clique de taille au moins k est un problème NP-Complet.
Une solution évidente consiste à tester tous les ensembles de k sommets (il y en a un nombre exponentiellement croissant avec k).
Coloriage de graphe
On appelle coloriage propre d’un graphe la donnée d’un entier (appelé couleur) pour chaque sommet tel que deux sommets reliés par une arête soient de couleurs différentes. Trouver le nombre minimum de couleurs qui permette d’obtenir une coloration propre pour un graphe est un problème NP-Complet.
Une solution évidente consiste à tester tous les coloriages possibles avec 1 couleur, puis 2 etc. Cet algorithme demande un nombre exponentiel de tests.
Cet exemple est décrit avec plus de détails dans la fiche ici.
P = NP ?
Une question qui challenge les informaticiens depuis très longtemps est de savoir s’il existe un problème NP qui ne soit pas dans P. Aujourd’hui personne ne sait si ces deux classes sont identiques ou non.
Si vous trouvez un algorithme répondant à un problème NP-Complet qui soit de complexité polynomiale, vous allez devenir très vite riche et célèbre !