Le plus grand problème de l’informatique : P versus NP

Il existe sept problèmes mathématiques jugés si difficiles et si intéressants que l’Institut de mathématiques Clay les a appelés problèmes du millénaire : celui qui résout l’un d’eux reçoit un million de dollars. L’un de ces problèmes touche aussi à l’informatique et s’appelle le problème P versus NP. Expliquons de quoi il s’agit.

Eh oui. Ne nous racontons pas d’histoires : ce ne sera pas simple à expliquer. Après tout, c’est un problème du millénaire. Va donc te préparer un bon thé vert 🍵 et c’est parti. Nous allons d’abord voir quatre problèmes différents du monde de l’informatique et des algorithmes. Nous les analyserons et nous verrons quel rapport ils ont avec les lettres P et NP.

Problème n° 1 : trouver le plus petit nombre

P versus NP concerne les algorithmes et leur complexité. Imagine que je renverse devant toi cent petits papiers, avec un nombre écrit sur chacun, et que je te demande de me trouver celui qui porte le plus petit nombre. Combien de temps cela va-t-il te prendre ?

Une demi-minute ? Deux minutes ?

Ces unités de temps ne nous intéressent pas vraiment en informatique théorique. Ce qui nous intéresse, c’est plutôt le nombre d’opérations. Nous pourrions donc poser la question autrement : combien de papiers dois-je examiner pour être sûr d’avoir trouvé le plus petit nombre ? La réponse est que je dois les examiner tous – car le plus petit nombre peut très bien se trouver sur le dernier papier. Si je jette devant toi cent papiers, tu dois en examiner cent. Si je t’en jette mille, tu dois en examiner mille. En général, si je jette devant toi n papiers, tu dois examiner n papiers.

C’est ce que nous appelons la complexité d’un algorithme. Si je jette devant toi n papiers et que tu dois effectuer n opérations pour trouver le plus petit nombre, cela signifie que cet algorithme de recherche du plus petit nombre a une complexité n, qu’on appelle aussi complexité linéaire, car la complexité est décrite par une fonction linéaire.

Bien, tu as parcouru les cent papiers et tu m’as annoncé que le plus petit nombre est 17. Comment puis-je vérifier que tu dis vrai ? Il n’existe pas d’autre moyen que de reparcourir tous les papiers et de vérifier qu’aucun ne porte un nombre plus petit. Autrement dit, tu dois regarder n papiers pour trouver le plus petit nombre, et moi, pour le vérifier, je dois faire la même chose. La complexité de la vérification du résultat est donc elle aussi n, une complexité linéaire.

Existe-t-il des algorithmes pour lesquels il est plus simple de vérifier le résultat que de le trouver ?

Problème n° 2 : le produit d’une paire

Imagine que je dépose devant toi deux tas de papiers de même taille, avec encore un nombre sur chaque papier. Je voudrais maintenant que tu trouves un nombre du tas A et un nombre du tas B dont le produit vaut 918. Par exemple, prenons ces deux tas de nombres :

$$\begin{array}{rcl}A& =& \{49;11;32;54;15\}\\ B& =& \{17;64;74;61;21\}\end{array}$$

Comment trouver un couple de nombres dont le produit est égal à 918 ? Eh bien, on peut tout simplement essayer toutes les possibilités. Combien y en a-t-il ? Pas mal : il y en a 25. Commençons par multiplier le premier nombre du tas A, c’est-à-dire 49, par chaque nombre du tas B :

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Aucun couple ne donne 918. Nous essayons donc la même chose avec les autres nombres du tas A, c’est-à-dire cinq autres paires pour le nombre 11, cinq autres pour le nombre 32, cinq autres pour 54 et les cinq dernières pour 15. Au total, nous pouvons donc essayer 25 paires de nombres. Finalement, nous trouvons que 54 · 17 = 918.

Quelle est la complexité de cet algorithme ? Ce qui nous intéresse, c’est le nombre de paires que nous avons dû multiplier. Les deux tas contenaient cinq papiers et nous avons dû essayer chacun des cinq nombres du premier tas avec chacun des cinq nombres du second. Au total, nous avons essayé 5 · 5 = 25 combinaisons. Si je jetais devant toi deux tas de 10 papiers, tu devrais essayer 10 · 10 = 100 combinaisons. En généralisant, si je jette devant toi deux tas de n papiers, tu dois essayer n · n = n² combinaisons.

Nous dirons que notre algorithme a une complexité n², une complexité quadratique, car elle est décrite par une fonction polynôme du second degré.

Mais est-il difficile de vérifier le résultat ? Si tu me réponds que 54 et 17 sont deux nombres dont le produit est 918, je n’ai pas besoin de parcourir toutes les paires des deux tas comme tu as dû le faire. Il me suffit de multiplier cette seule paire 54 · 17 pour savoir si tu as raison ou non. Ainsi, alors que pour résoudre ce problème il faut calculer jusqu’à n² produits, pour le vérifier il suffit de calculer un seul produit. La vérification a donc une complexité constante, égale à 1.

C’est ce qui distingue nettement ce problème du précédent, où il fallait le même nombre d’étapes pour le calcul lui-même et pour la vérification qui suivait.

Ce problème est aussi de plusieurs ordres de grandeur plus complexe que le précédent. Si je renversais devant toi dix mille papiers en te demandant de trouver le plus petit nombre, tu y arriverais sans doute en une journée. Mais si je renversais deux fois dix mille papiers et que je te laissais chercher le produit, tu devrais examiner dix mille fois dix mille produits, soit cent millions de calculs. Même en essayant un produit par seconde, cela te prendrait environ trois ans.

Problème n° 3 : la somme d’un sous-ensemble

Passons au troisième problème. Cette fois, je dépose devant toi douze papiers portant des nombres et je voudrais que tu trouves un nombre quelconque de papiers dont la somme vaut zéro. Par exemple :

$$A=\{24;-69;1;-15;-76;-60;16;-83;48;-22;54;-47\}$$

Choisis dans ces nombres un groupe dont la somme est égale à 0. Par exemple, les nombres

$$24+48-69+1$$

donnent une somme de 4 et ne constituent donc pas la bonne réponse. La bonne réponse est le groupe de nombres… et sais-tu quoi ? Essaie de la trouver toi-même, comme devoir à la maison 😉. Il n’existe qu’un seul groupe de nombres dont la somme vaut 0. Au moins, tu verras à quel point ce problème est difficile.

Il nous faut maintenant connaître la complexité de ce problème. Le calcul lui-même n’est plus tout à fait trivial et s’adresse plutôt aux amateurs de subtilités. Si tu veux savoir comment calculer la complexité de ce problème, poursuis ta lecture. Sinon, tu peux passer au chapitre suivant. ⏩

Comment donc trouver un groupe de nombres dont la somme vaut 0 ? Eh bien, il faut tout simplement essayer toutes les combinaisons possibles de nombres. Nous devons essayer toutes les paires de nombres, tous les triplets, les quadruplets, les quintuplets, etc., et vérifier pour chaque groupe si sa somme est nulle. Combien existe-t-il de telles combinaisons ?

Voyons-le sur un ensemble plus petit. Combien de groupes différents de nombres, c’est-à-dire de sous-ensembles, puis-je former à partir des trois nombres B = {5 ; 7 ; 9} ? Il y en a huit en tout :

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5;9\}\\ B_6& =& \{5;7\}\\ B_7& =& \{7;9\}\\ B_8& =& \{5;7;9\}\end{array}$$

Remarque que nous avons aussi compté le sous-ensemble vide B₁. Il n’est pas très utile pour le moment, mais par souci d’exhaustivité nous l’avons gardé. Pour simplifier le calcul, nous associons à chaque sous-ensemble un vecteur binaire. Un vecteur binaire est tout simplement une suite de 0 et de 1, par exemple 00101010. Nous allons travailler avec des vecteurs binaires de longueur trois. Nous associons le vecteur 101 au sous-ensemble qui contient « le premier et le troisième nombre de l’ensemble de départ, mais pas le deuxième », c’est-à-dire à l’ensemble {5 ; 9}. Nous associons le vecteur 110 au sous-ensemble qui contient « le premier et le deuxième nombre de l’ensemble de départ, mais pas le troisième », c’est-à-dire à l’ensemble {5 ; 7}, et ainsi de suite.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5;9\}& \to & 101\\ B_6=\{5;7\}& \to & 110\\ B_7=\{7;9\}& \to & 011\\ B_8=\{5;7;9\}& \to & 111\end{array}$$

Nous voyons que chaque sous-ensemble correspond à exactement un vecteur binaire de longueur trois, et que chaque vecteur binaire de longueur trois correspond à exactement un sous-ensemble. Donc, si nous calculons combien il existe de vecteurs binaires différents de longueur n, nous obtenons le nombre de combinaisons différentes que nous pouvons former à partir de n nombres différents. Calculons-le.

Il existe deux vecteurs binaires de longueur un : 0 et 1.

Pour obtenir les vecteurs binaires de longueur deux, nous prenons tous les vecteurs binaires de longueur un et nous ajoutons un 0 à la fin de chacun : nous obtenons les vecteurs 00 et 10. Nous reprenons tous les vecteurs de longueur 1 et nous ajoutons un 1 à la fin : 01 et 11. Nous avons ainsi obtenu tous les vecteurs de longueur 2 : 00, 01, 10 et 11.

Pour obtenir les vecteurs binaires de longueur trois, nous prenons tous les vecteurs binaires de longueur deux et nous ajoutons à la fin un zéro : 000, 010, 100 et 110, puis un un : 001, 011, 101 et 111.

Et ainsi de suite pour chaque longueur suivante. Nous voyons que lorsque nous augmentons de un la longueur du vecteur binaire, le nombre de vecteurs binaires différents double. Pour une longueur de quatre, nous obtiendrions donc en tout 2 · 2 · 2 · 2, soit 16 combinaisons différentes.

En général, nous pouvons établir que si un ensemble M contient n éléments, le nombre de tous les sous-ensembles de M est égal au nombre de tous les vecteurs binaires différents de longueur n, c’est-à-dire à

$$\underset{n\text{ fois}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ ou n² : bonnet blanc et blanc bonnet ? 🤷‍♂

Il existe donc 2ⁿ sous-ensembles différents que l’on peut former à partir d’un ensemble de n nombres. Dans notre cas, nous avons n = 12 nombres et nous devons donc vérifier 2¹² combinaisons différentes, soit 4096 combinaisons. Nous dirons que ce problème a une complexité 2ⁿ, une complexité exponentielle, car il est décrit par une fonction exponentielle.

Remarque que le problème précédent avait une complexité n², alors que celui-ci a une complexité 2ⁿ. Cela ressemble beaucoup, non ? Mais il y a une grande différence entre un exposant constant et une variable n en exposant. Remarque que, pour n = 4, nous obtenons

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Bien, pour l’instant nous trouvons la même chose. Et pour n = 10 ?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Eh bien, la fonction exponentielle a décollé et elle est déjà environ dix fois plus grande que la fonction polynôme du second degré. Qu’obtient-on pour n = 20 ?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

Pour n = 20, la complexité exponentielle a une valeur environ 2 600 fois plus élevée que la complexité quadratique. Nous voyons donc que la fonction exponentielle croît beaucoup plus vite que la fonction polynôme du second degré. Pense-y la prochaine fois qu’une pandémie se propagera dans la population à une vitesse exponentielle.

Si je jetais donc devant toi vingt papiers, tu devrais examiner 1 048 576 combinaisons. Ça fait beaucoup.

Comment vérifier que le résultat est correct ?

Combien de temps me faudra-t-il pour vérifier que le groupe de nombres obtenu a bien une somme égale à 0 ? Ce sera assez rapide : je fais tout simplement la somme de ce groupe de nombres, et si elle est égale à 0, tu as trouvé le bon groupe de papiers ; si la somme est différente, tu as trouvé un mauvais ensemble de papiers.

Nous voyons de nouveau que vérifier un résultat est de plusieurs ordres de grandeur plus simple que de le trouver.

Problème n° 4 : le problème du voyageur de commerce

Le problème du voyageur de commerce est l’un des problèmes algorithmiques les plus célèbres. En gros, nous avons un voyageur de commerce qui vend de la pluie. Et ce voyageur de commerce doit beaucoup voyager pour gagner sa vie. Il a donc décidé de visiter les 14 plus grandes villes de France. Et comme il ne veut rien gaspiller, il a décidé de trouver le chemin le plus court possible qui le mène dans toutes ces villes. Notre mission est de trouver ce chemin le plus court.

Comment trouver ce chemin le plus court ? Nous essayons toutes les possibilités.

Nous pouvons simplifier les choses. Imaginons qu’entre deux de ces villes il existe toujours exactement un chemin le plus court. Comment trouver le chemin le plus court passant par toutes les villes ? Nous avons 14 villes. Nous avons donc 14 possibilités pour commencer. Supposons que nous partions de Marseille ! Où pouvons-nous aller depuis Marseille ? En théorie, nous pouvons aller dans n’importe quelle autre ville de la liste. Nous pouvons donc choisir parmi les 13 villes restantes.

Nous pouvons déjà compter que nous avons en tout 14 · 13 possibilités pour visiter les deux premières villes – 14 possibilités pour commencer, puis un choix parmi les 13 villes restantes.

Quand nous arrivons dans la deuxième ville, nous devons continuer. Nous sommes déjà passés par deux villes, nous pouvons donc partir vers l’une des 12 villes restantes. Nous avons ainsi en tout 14 · 13 · 12 possibilités pour visiter les trois premières villes.

Une fois la troisième ville visitée, nous devons choisir l’une des 11 villes restantes, puis l’une des 10 villes restantes, etc.

Quand nous les aurons toutes visitées, nous constaterons que nous avions le choix entre

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

possibilités. Cela peut te rappeler la factorielle, que l’on note avec un point d’exclamation. Nous pouvons donc dire que ce produit est égal à 14! :

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

et il existe donc 14! chemins qui passent par les 14 plus grandes villes de France. Est-ce beaucoup ? Plutôt, car

$$14!=87178291200.$$

En général, si nous cherchions le chemin le plus court entre n villes, nous devrions essayer n! chemins différents. La complexité de cette résolution est donc n!.

Comment vérifier que nous avons trouvé le bon résultat ? Si tu me disais que le chemin le plus court va de Lille à Marseille, puis à Lyon, etc., comment pourrais-je vérifier que tu dis vrai ? Eh bien, difficilement 🤷‍♂. En regardant ce chemin, je n’ai aucun moyen simple de vérifier s’il est justement le plus court. Je dois en fait refaire tout le calcul. La complexité de la vérification du résultat est donc, elle aussi, n!.

Les classes P et NP

Nous avons vu quatre problèmes et les algorithmes qui les résolvent, et nous avons analysé la difficulté de trouver la solution et celle de la vérifier. Nous pouvons résumer cela dans ce tableau :

Répartissons maintenant nos problèmes en deux groupes. Le premier groupe sera formé des problèmes faciles à résoudre. Ce sont les problèmes qui se résolvent avec une complexité n, ou n², ou n³, ou n⁴, etc. Comme des expressions telles que n² s’appellent des polynômes, nous désignons cette classe de problèmes par la lettre P. Nous disons donc que la classe P contient les problèmes qui peuvent être résolus en temps polynomial (= ils ont une complexité du type n² ou n⁷). En gros, ce sont des problèmes qui se résolvent plus ou moins facilement.

Le problème n° 1, trouver le plus petit nombre, appartient donc à la classe P, car sa complexité de résolution est n, et le problème n° 2, le produit d’une paire, y appartient aussi, car sa complexité de résolution est n² : dans les deux cas, ce sont des polynômes.

La seconde classe est la classe NP. Elle contient les problèmes qui peuvent être vérifiés en temps polynomial. Tous nos problèmes, sauf le dernier, appartiennent donc à la classe NP. Le problème du voyageur de commerce, nous ne savons pas le vérifier en temps polynomial. Les trois problèmes précédents peuvent être vérifiés en temps polynomial.

Le problème du voyageur de commerce, nous ne savons ni le résoudre ni le vérifier en temps polynomial. Pour le problème du voyageur de commerce, il nous faudrait donc encore une autre classe, qui contiendrait des problèmes encore plus difficiles. Cette classe existe, mais elle ne nous intéresse pas pour le moment.

Il est clair que la classe P est un sous-ensemble de la classe NP. Autrement dit, tout problème de la classe P est aussi dans la classe NP. Cela se comprend – si nous sommes capables de résoudre un problème en temps polynomial, nous sommes aussi capables de vérifier le résultat en temps polynomial.

Le problème P versus NP

Et l’inverse est-il vrai ? Tout problème de la classe NP est-il aussi dans la classe P ? Autrement dit, s’il existe un moyen de vérifier le résultat d’un problème en temps polynomial, existe-t-il aussi un algorithme qui résoudrait ce problème en temps polynomial ?

Par exemple, nous savons que nous sommes capables de vérifier le résultat du problème n° 3, la somme d’un sous-ensemble, en temps polynomial. Mais pour le résoudre, nous avons utilisé un algorithme qui n’est pas polynomial : l’algorithme utilisé a une complexité exponentielle 2ⁿ. Sommes-nous pour autant certains qu’il n’existe aucun algorithme de complexité polynomiale pour ce problème ?

Non, nous ne le savons pas !

Il se pourrait très bien que, pour tout problème qui peut être vérifié en temps polynomial, il existe un algorithme qui résout ce problème en temps polynomial. Nous ne le savons pas. Nous ne savons pas démontrer l’existence d’un tel algorithme, mais nous ne savons pas non plus réfuter son existence.

Si, pour tout problème de la classe NP, il existait un algorithme qui le résout en temps polynomial, cela signifierait que la classe NP serait en fait égale à la classe P. Tous les problèmes de la classe P seraient dans la classe NP et tous les problèmes de la classe NP seraient dans la classe P – les deux classes seraient égales, identiques.

Le problème P versus NP est donc la question de savoir si la classe P est identique à la classe NP, ou s’il s’agit de deux classes de problèmes différentes.

Soit P = NP, soit P ≠ NP. Personne ne le sait et, si tu le découvres, un million de dollars, une gloire éternelle et probablement aussi le prix Turing, une sorte de prix Nobel des informaticiens, t’attendent.

Que se passerait-il si P = NP ?

Que se passerait-il si P = NP ? Eh bien, il n’est pas facile de le dire. Nous saurions que, pour tous les problèmes de la classe NP, il existe un algorithme qui les résout en temps polynomial. Par exemple, que pour notre problème n° 3, la somme d’un sous-ensemble, il existe un algorithme qui le résout en temps polynomial. Seulement voilà, il y a trois bémols :

• Savoir qu’un tel algorithme existe ne signifie pas que nous sommes capables de le trouver. Nous saurions simplement que oui, il existe un algorithme qui résout le problème en temps polynomial, mais nous ne saurions peut-être pas le construire avant cent ans. C’est un peu comme la relativité générale, qui a prédit l’existence des trous noirs, mais il nous a tout de même fallu plusieurs décennies de plus pour réaliser la première « photographie » d’un trou noir.
• L’existence d’un algorithme de temps polynomial ne signifie malheureusement pas encore qu’il est rapide. Nous pourrions trouver un algorithme de complexité n¹⁰⁰. Car l’expression n¹⁰⁰ est elle aussi un polynôme. Si nous comparons les complexités 2ⁿ et n¹⁰⁰, nous constatons que, tant que n est relativement petit, l’algorithme de complexité 2ⁿ a encore besoin de moins d’opérations. Par exemple, pour n = 20, on a 2²⁰ = 1 048 576, alors que l’expression 20¹⁰⁰ donne un nombre d’environ 130 chiffres, soit un nombre supérieur de 120 ordres de grandeur à 1 048 576. Notre algorithme polynomial serait donc, en réalité, plus lent que l’algorithme exponentiel. Du moins tant que n est relativement petit.
• Si nous parvenions tout de même à trouver un algorithme rapide de temps polynomial, nous pourrions résoudre beaucoup de problèmes plus vite et avec plus de précision. C’est évidemment une bonne nouvelle, mais elle a aussi ses mauvais côtés. Il existe un domaine qui repose sur le fait que certains problèmes sont difficiles à résoudre : la cryptographie – le chiffrement. Il pourrait donc arriver qu’il devienne bien plus simple de casser les chiffrements actuels.

Intermède : puisque tu as lu jusqu’ici, je te révèle, en récompense, que la solution du problème n° 3 est 24 + 1 − 60 + 16 − 83 + 48 + 54.

Que se passerait-il si P ≠ NP ?

Si les classes de problèmes P et NP étaient différentes, il ne se passerait pas grand-chose, car c’est plus ou moins le statu quo. À l’heure actuelle, nous n’avons aucun algorithme qui résolve en temps polynomial un problème difficile de NP, et si quelqu’un démontrait que P ≠ NP, les choses resteraient simplement ainsi pour toujours. La vraie sensation serait la démonstration que P = NP.

Références dans la culture populaire

• Dans un épisode des Simpson, on voit Homer entrer dans une sorte de réalité alternative où il a la révélation que P = NP. À voir sur youtube.com.
• Dans Futurama, on voit à l’inverse qu’ils ont en réserve deux dossiers, l’un intitulé P et l’autre NP. À voir sur youtube.com.
• Le deuxième épisode de la deuxième saison de la série Elementary, intitulé « Échec et Maths », est consacré au meurtre d’un mathématicien qui avait probablement résolu le problème P versus NP.