P=NP

Divers Vie intérieure / Pensées

#LeSaviezVous : vous pouvez toucher 1 million de dollars si vous arrivez à résoudre un des 7 problèmes mathématiques mis à disposition par l’Institut Clay (en fait, il en reste 6, la Conjecture de Sicéron c’est Poincaré ayant été validée en 2006). Et parmi ces problèmes, se pose celui énoncé dans le titre :

P = NP

Mais encore ?

Pour essayer de simplifier au maximum la compréhension de l’équation, cela revient à se demander si vérifier le résultat d’une solution à un problème rapidement pourrait faire en sorte de trouver ce résultat tout aussi rapidement.

Si l’on se base sur les modèles décisionnels (et d’une manière générale sur des problèmes polynomiaux, donc à plusieurs paramètres), où l’on est obligé d’analyser un grand nombre de cas avant de trouver la meilleure solution, on se rend vite compte que la vérification de la solution est toujours bien plus rapide que la réflexion qui l’a précédée. Mais si, par cette approche, on arrivait à la bonne solution dans le même temps que sa vérification, on tiendrait un véritable Graal mathématique !

L’exemple de l’Institut est assez éloquent :

Supposons que vous soyez chargé de loger un groupe de quatre cents étudiants. Le nombre de places est limité, seuls cent étudiants se verront attribuer une place dans la résidence universitaire. Pour compliquer les choses le doyen vous a fourni une liste de paires d’étudiants incompatibles, et demande que deux étudiants d’une même paire ne puissent jamais apparaître dans votre choix final.

Il est important de comprendre deux notions fondamentales, complémentaires :

  • le déterminisme, c’est que l’on trouve dans le principe de causalité (cause-effet) et dans toutes les opérations mathématiques linéaires
  • et sa corrélation le non-déterminisme, où l’on ne peut déduire de manière aisée une solution, uniquement en comparant les différents résultats à l’objectif de la problématique. L’exemple le plus connu est celui du voyageur de commerce, qui doit lier toutes les villes par le chemin le plus court possible…

Et à quoi ça sert ?

Là, comme ça, tout de suite maintenant, de but en blanc, à rien. D’une part, je n’avais pas grand chose à raconter sur ma vie, et d’autre part, je me disais qu’il y a des personnes qui seraient intéressées pour gagner 1 million de dollars rien qu’en se triturant les circonvolutions cérébrales (et en grattant quelques ramettes de papier).

Et cela montre aussi qu’il y a 3 manières d’y répondre :

  1. on montre qu’il est possible que P=NP, en changeant de manière fondamentale les processus de traitement de l’information (notamment en travaillant sur de l’expérientiel, du non-linéaire, etc.)
  2. on montre qu’il est impossible que P=NP, ce qui est déjà le cas dans les modèles mathématiques admins
  3. on montre que P=NP est indémontrable par les connaissances actuelles, voire futures. Et cela montrerait toute l’humilité que l’on attend des sciences.

Cette approche dans les réponses possibles montre plusieurs choses :

  • Il existe des questions sans réponse, et il en sera toujours ainsi pour ces mêmes questions
  • Il n’existe pas de réponse immuable, car il peut être possible de démontrer que P=NP est rigoureusement impossible aujourd’hui mais qu’il le sera demain. Et de ce fait, peut-être que le second gars ne touchera pas son million de dollars…

Et que, quelque part, la réponse n’est pas la chose la plus importante, car pour le commun des mortels, la solution à cette énigme ne changera absolument rien à leur quotidien, sauf à admettre que tout n’est pas blanc ou noir, et que tous les savoirs n’ont pas pour vocation à être découverts.