(En lisant entièrement cette note, vous pourrez peut-être gagner un millions de dollars)

Voyageur de commerce, quel beau métier ! Se balader de maisons en maisons pour vendre de chouettes encyclopédies !... Mais comment peut-on aujourd'hui songer à faire ce métier quand on sait qu'il va falloir passer son temps à marcher entre toutes les maisons...
"Et si, avec mes compétences d'informatiques, j'écrivais un algorithme qui me chercherait le moyen le plus court de relier toute les maisons ! Avec ça, je pourrais minimiser mon temps à marcher, et passer plus de temps à vendre ma camelote !". Après cette réflexion, Norbert Petiot se mit à programmer, il trouva se qu'il chercha : un algorithme qui trouve le plus court chemin entre n points. Il fait un petit test simple, avec 4 points. Le programme teste alors les 12 chemins possible et retourne en un centième de seconde le meilleur chemin.

commerce

Parfait, se dit-il, devant ce jeu d'essai. Il décide alors de rentrer ses données, les 15 maisons qu'il veut visiter et les 105 distances qui séparent chaque maison 2 à 2... Cette histoire a plus de 17 ans... On dit qu'il attend encore la réponse à son problème... (Plus que 96 jours à attendre, finalement)

Mais que s'est-il donc passé ? Pourquoi ce malheureux voyageurs de commerce est mort de faim devant son écran en se disant "plus que quelques secondes à attendre" ? A t-il mal réalisé son programme ?

Eh bien, il se trouve que Herbert s'est frotté à un problème NP-complet...

NP-complet ? Qu'est ce que c'est que cette bête là ?!
(Les histoires de théorie de la complexité étant plus compliquée qu'il n'y parait, il y aura un certain nombre de simplifications fort peu précises)
Pour résoudre un problème en informatique, on a tendance à utiliser des algorithmes. En théorie, on peut calculer n'importe quoi. En théorie seulement, puisque dans la pratique, on est toujours limités par la puissance des ordinateurs que l'on utilise. C'est pour cela que l'on peut catégoriser les différents problèmes par leur facilité à être résolus par des ordinateurs. Parmi ces différentes catégories, on parle surtout des classes P et des classes NP.

La classe P (polynomial)

"Voici une boîte d'allumettes avec n allumettes. Fonctionnent t-elles toutes ?". Pour le savoir, il va falloir essayer toutes les allumettes en les allumant. Si elles fonctionne toutes, on pourra répondre oui à la question. Le temps dont on aura besoin pour le savoir sera donc proportionnel au nombre d'allumettes.

"Y a-t-il un couple qui s'est formé pendant cette soirée comportant n personnes ?". Sachant que personne ne voudra vous répondre, il va donc falloir vérifier pour chaque couple s'il correspondent à l'idée qu'on se fait d'un couple. Le temps qui va falloir pour trouver la réponse sera donc proportionnel au nombre de couples que l'on peut former, et donc, proportionnel (à quelque chose près) à n².
On dit qu'on problème de décision (auquel on peut répondre oui ou non) est de classe P si on peut trouver un algorithme qui donnera une réponse certaine en un temps polynomial.

La classe NP (non-déterministe polynomial)

"Étant donné n villes, existe-t-il un chemin passant par tous ces villes de longueur inférieure à N ?". Avec un peu de chance, on va pouvoir répondre oui très rapidement, sinon, le temps d'attente sera proportionnel à n!
Pour simplifier de manière atroce, les problèmes NP sont les problèmes dont le temps d'exécution, si on manque de chance, ne sera pas polynomial.
Et les problèmes NP-complet (ou NP-difficile en simplifiant) dans cette histoire ? Et bien, c'est l'ensemble des problèmes qui ressemblent à notre problème du voyageur de commerce (qui est NP-complet), c'est à dire, les problèmes dont l'algorithme de résolution ressemble (même de loin) à celui du problème du voyageur de commerce.

Quelques exemples de problèmes NP-complets :

Problème du circuit hamiltonien
"Étant donné un graphe, y existe t-il un cycle hamiltonien ?"
Alias, étant donné un graphe, existe t-il un chemin passant une et unique fois par tous les points ?

hamilton1
Peut-on trouver un cycle hamiltonien dans ce graphe ?... Réponse...

Problème de la séparation équitable
"Étant donné une suite d'entiers données, y a t-il moyen de la séparer en deux paquets de même somme ?"

Exemple : 1, 2, 2, 3, 3, 4, 5...
Réponse : Oui : 2+2+3+3=1+4+5

Problème du sudoku
"Ce sudoku n²×n² cases est-il faisable ?"

Sudoku
Exemple : ce sudoku est-il faisable ?... Réponse...

Problème des équations quadratiques diophantiennes
"L'équation ax²+by=c, avec a,b,c entiers donnés, admet-elle des solutions ?..."

Problème de Laurent Romejko
"Quel est le mot le plus long existant parmi ces n lettres" et "Avec des additions, soustractions, multiplications et divisions, peut-on obtenir une certaines sommes avec n chiffres donnés"...

Bref
Il existe énormément de problèmes NP-complet, et en résoudre un seul de manière déterministe (avec un algorithme polynomial) suffirait à empocher la somme de un millions de dollars...

Plus d'informations dans le prochaine article, parce cet article-là est déjà trop long.