Pourquoi j'adore les maths

La question P = NP (2)

Donc, tandis qu'en théorie de la calculabilité le travail consiste à montrer s'il existe un algorithme pour résoudre tel ou tel problème, en théorie de la complexité on cherche s'il existe un algorithme efficace ; par exemple, on veut savoir s'il y a un algorithme polynomial ou non.

Gudule : qui ne sert toujours à rien si c'est puissance 1000.

Certes. Au passage, on en profite pour comprendre nos problèmes et leur comportement en profondeur. Par exemple, on démontre un résultat de NP-complétude.

Gudule : je viens de me faire insulter, là, maître, pas vrai ?

« P » est la « classe » qui regroupe les problèmes admettant un algorithme polynomial pour les résoudre, donc avec un nombre polynomial d'opérations. « NP » c'est la classe qui regroupe les problèmes qui ont un algorithme polynomial pour vérifier une solution. C'est pas pareil. Vous devinez que « NP » est un monde beaucoup plus gros.

« NP-complets » sont les problèmes de NP qui sont plus durs que tous les autres. Ce sont les porte-étendards de l'armée. Si vous avez un algorithme pour résoudre un problème NP-complet avec un certain nombre d'opérations, alors au prix d'une multiplication par un nombre polynomial (n puissance 4, 10, on s'en fiche toujours un peu) d'opérations, vous pouvez utiliser cet algorithme pour résoudre tous les problèmes NP.

D'une certaine manière, les problèmes NP-complets sont tous « similaires », tous un peu différents et tous aussi difficiles d'un point de vue strictement théorique. Il en existe des milliers et certaines personnes s'amusent à en faire des listes.

Le problème de Gudule faisant les courses est NP-complet.

Gudule : et alors ? Pourquoi m'avoir retiré la feuille des mains ? J'avais presque trouvé un bon algorithme.

À l'heure actuelle, la relation exacte entre P et NP est inconnue. Comprendre : on ne sait pas si P = NP. On ne sait pas si, pour tout problème dans NP, il existe un algorithme polynomial pour le résoudre. C'est quand même fâcheux. Et rageant.

Vu la tête des problèmes dans NP, vu leur degré de difficulté, et vu que depuis des décennies tout le monde se casse la tête sur ces questions, la plupart des chercheurs en informatique pensent que P est différent de NP. Mais il n'existe pas de preuve avérée de ça. C'est même pire : vous trouvez sur Internet des milliers de preuves farfelues faites par des gens qui pensent être dans leur bon droit, donc si un jour quelqu'un trouve une preuve correcte, il aura du mal à se faire entendre.

La plupart du temps, une (fausse) preuve de « P est différent de NP » va contenir la phrase suivante :

et là, on remarque qu'on ne peut pas calculer en faisant moins d'opérations que...

« On ne peut pas » est rédhibitoire, tant qu'on ne l'a pas correctement démontré, c'est ce qui rend la théorie de la complexité intéressante et difficile, et c'est ce qui rend la plupart de ces « preuves » fausses.

Comme le problème de Gudule faisant les courses est NP-complet, je lui conseillerais plutôt d'arrêter de chercher un algorithme « polynomial » pour le résoudre, et de se consacrer à employer les méthodes de résolution génériques des problèmes NP-complets... car ce n'est pas parce que c'est « réputé difficile » d'un point de vue théorique qu'on ne peut pas s'en sortir très bien avec des méthodes ad hoc. Après tout, dans certains cas pratiques, il vaut mieux deux à la puissance « n fois 0,00000000001 » plutôt que n à la puissance 1000.

FTM : c'est une belle moralité. Je suis ému.

Et nul doute que cette question, même si elle fait un quasi-consensus, continuera d'agiter les cauchemars des informatheux pour assez longtemps. Le créateur des maths ne manque pas d'ironie.

FTM (lance de ses yeux globuleux un regard qui fait peur) : hé, hé, hé.

---------------------

Gudule : on avait promis les fractales, maître.

Ah, Gudule, justement, j'avais besoin d'un larbin pour programmer. Allez, au travail. On avait promis les fractales, Gudule, il faut dessiner des belles fractales maintenant.

Gudule : gné.