1. Page d'accueil
  2. Les mathématiques et théories abordées
  3. Par discipline
  4. Informatique Théorique

P versus NP


Histoire de vous mettre l’eau à la bouche, le problème " P vs NP " a été choisi pour être l’un des 7 problèmes du millénaire par l’institut de mathématiques de Clay. Résoudre ce problème peut vous faire gagner $1 000 000. [1]

En informatique théorique, il y a de nombreux domaines de recherches. Parmi ceux-ci, on peut citer : la théorie de la calculabilité et la théorie de la complexité. La théorie de la calculabilité cherche à savoir si un problème peut être résolu par un ordinateur. La théorie de la complexité cherche à savoir si les problèmes calculables peuvent être résolu efficacement ou pas.

Bien sûr, il a fallut définir ce qu’on entendait par " calculabilité " (Thèse de Church-Turing) et par " ordinateur " (Idéalisé en " Machine de Turing ") pour pouvoir établir ces théories, mais cela n’a pas grande importance pour notre propos.

Une fois que l’on sait que l’on peut résoudre un problème avec un ordinateur, on se demande rapidement si cette résolution va pouvoir se faire efficacement ou pas. Pour cela, les mathématiciens ont classé les problèmes dans des ensembles appelés " Classes ".

Avant de continuer la description de ces classes, il faut que j’introduise quatre notions :

Un algorithme est une " recette " qui décrit une suite d’opération à réaliser pour calculer le résultat. Vous en utilisez tous les jours sans vous en apercevoir. Par exemple, pour faire bouillir de l’eau :

Un algorithme déterministe est un algorithme qui à chaque étape passera toujours à l’étape suivante de la même façon : celle prévue par le concepteur de l’algorithme. S’il y a un choix à faire, il fera toujours le même choix si on l’exécute avec les mêmes données en entrée. L’algorithme ci-dessus est bien sûr déterministe.

Un algorithme non déterministe est un algorithme qui, lorsqu’il se trouve face à un choix, peut indifféremment choisir l’un ou l’autre des chemins d’exécution sans que l’on ne puisse prédire à l’avance celui qu’il va choisir. De manière imagée, on s’imagine qu’il se dédouble pour exécuter les différents choix simultanément jusqu’à aboutir à tous les résultats possibles. Il arrive donc à résoudre les problèmes bien plus vite qu’un algorithme déterministe. Seulement voilà : ces algorithmes ne peuvent s’exécuter que sur des ordinateurs non déterministe et ces machines ne sont pas constructibles. Il est possible de transformer un algorithme non déterministe en algorithme déterministe (il suffit de calculer tous les chemins possibles l’un après l’autre plutôt que simultanément), mais au détriment de la durée de calcul qui peut exploser.

Pour illustrer la différence entre un algorithme déterministe et un algorithme non déterministe, prenons le problème suivant : " 1241 n’est pas un nombre premier ". L’algorithme doit répondre vrai ou faux. Un algorithme déterministe va faire :

Jusqu’à aboutir soit à trouver un diviseur, et conclure que la proposition est vraie, soit ne pas en trouver un et constater que c’est faux. Au pire, il aura fait 1239 divisions pour tester.

L’algorithme non déterministe va simplement répondre : vrai, 1241=17*73. Divination ? Un peu. En fait, l’algorithme non déterministe évalue tous les cas simultanément et trouve donc immédiatement s’il y en a un qui répond à la question.

La complexité algorithmique permet de classer les algorithmes entre eux. Prenons le cas d’un tri. Supposons que vous ayez un tas de livres que vous souhaitez classer par ordre alphabétique. Comment faites-vous ? La plupart des gens commenceront de la gauche vers la droite :

Ce tri est appelé " tri par insertion " (on insère chaque livre à sa place parmi les livres déjà triés). Dans le pire des cas (si les livres étaient triés par ordre alphabétique inverse), il faudrait n*(n-1)/2 échanges (avec n le nombre de livres). On dit que la complexité de ce tri est O(n2). [2]

Cela permet donc de connaître l’évolution du temps de calcul lorsqu’on augmente le nombre de données ou la taille des données à traiter.

La dernière notion nécessaire est le problème de décision. En informatique, on peut traduire n’importe quel problème en une question qui n’a pour réponse que " Oui " ou " Non ". Ainsi, le problème de tri précédent peut être traduit par : " la liste des livres triée est-elle : (aa, bb, cc, ...) ? ". Pour décider si la réponse est oui ou non, il suffit de trier la liste et de comparer le résultat.

Les mathématiciens ont donc classé ces algorithmes avec les noms suivants :

(d’autres classes existent au-delà de NP, mais il n’est pas utile ici de détailler [3])

Une autre manière de présenter la classe NP est de dire que ce sont les problèmes qui, à partir d’une solution donnée, acceptent un algorithme de la classe P qui vérifie si la solution est vraie ou pas. Ainsi, résoudre une grille de Sodoku est un problème de classe NP si l’on considère une grille avec un nombre de carré n*n (les grilles des journaux ont une taille de 3*3) : il est " facile " de vérifier qu’une grille remplie est exacte, mais remplir la grille est bien plus compliqué. L’une des façons de résoudre un problème NP est d’avoir un algorithme deterministe qui calcule toutes les solutions possibles (et qui s’exécute en général en un temps exponentiel (O(en )) et dans un deuxième temps l’algorithme de la classe P qui se charge de tester chaque solution potentielle calculée. Vu ce que je viens de dire, on a trivialement :

P inclu dans NP

En effet, si un problème de décision peut être résolu par un algorithme déterministe en un temps polynomial, on peut évaluer qu’une réponse est exacte en un temps polynomial également (il suffit de calculer les réponses et de comparer la réponse proposée aux réponses calculée et le tour est joué).

La question à $1 000 000 est : peut-on dire que P=NP ou pas ?

Cette question a été posée pour la première fois en 1970 et n’a toujours pas de réponse. Cette réponse est importante parce que de nombreux problèmes que l’on utilise dans l’industrie sont dans la classe NP. L’un des problèmes célèbres est celui du voyageur de commerce : soit un nombre de ville n reliée chacune à ses voisines par une distance d, quel est le chemin le plus court permettant d’aller un fois et une seule dans chaque ville ? Les algorithmes de nos GPS font souvent ce calcul, mais ils ne sont jamais certain de vous proposer la bonne réponse : ils vous proposent la meilleure qu’ils aient trouvés après un temps maximal de calcul. Si on arrive à démontrer que P=NP, cela voudra dire que l’on peut tenter de trouver des algorithmes permettant de résoudre efficacement les problèmes de la classe NP au lieu de se contenter d’approximations comme on le fait aujourd’hui.

Il n’y a pas de consensus parmi les mathématiciens sur le résultat à trouver. Nombreux sont ceux qui soupçonnent que P est différent de NP, mais il y a de bons arguments dans les deux camps. On peut trouver ici une liste de tentatives de preuve des deux camps.

De toutes façons, dans les deux cas il y aura une avancée dans l’informatique. Si P=NP, on saura que l’on peut chercher des algorithmes efficaces pour résoudre les problèmes NP et il y aura de nombreuses avancées dans beaucoup de domaines (et quelques problèmes, parce que les cryptages actuels sont basés sur le fait qu’il est compliqué de trouver les facteurs premier d’un grand nombre (cf épisode 105), mais pas de panique : savoir qu’il y a un algorithme efficace ne voudra pas dire trouver l’algorithme immédiatement... cela fait tout de même quelques siècles qu’on cherche...). Si P est différent de NP, les chercheurs sauront qu’il est inutile de perdre du temps à chercher un algorithme efficace et ils se concentreront sur la recherche de la meilleure approximation possible.

Article par BubuLeMag. >> Réagir


[1] http://www.claymath.org/millennium/P_vs_NP/
[2] http://fr.wikipedia.org/wiki/Complexité_algorithmique
[3] http://fr.wikipedia.org/wiki/Théorie_de_la_complexité


Rédigé initialement par BubuLeMag.
Dans Informatique Théorique et Par nom
Dernière modification de la page le 06/08/2008 à 22h14.