Est-ce que la résolution de certains problèmes complexes doit rester hors de portée de l’humanité ? Pour le bien de tous, parfois on aurait préféré que oui 🙂
P = NP, ça n’a l’air de rien, mais c’est le problème le plus fondamental des mathématiques et de l’informatique théorique depuis plus de 50 ans.
P et NP sont 2 ensembles de problèmes de décision. Un problème de décision est une question dont la réponse est soit oui soit non. Par exemple, est-ce que 2 est un nombre pair ? Est-ce qu’il fera beau demain ? En programmation c’est le retour booléen d’une fonction de type prédicat.
L’ensemble des problèmes qui appartiennent à P, sont les problèmes pour lesquels il existe un algorithme polynomial. C’est à dire, au plus et dans le pire des cas, le nombre d’étapes de communication est inférieur ou égal à un polynôme (≤ O(n log n)), une puissance constante de n à la taille d’entrée au problème.
Un problème appartenant à la classe NP, a au moins un algorithme qui le résout (lentement) de façon exponentielle (e^x), mais sa vérification peut se faire de façon polynomiale (donc rapidement). Mais est-ce qu’on pourrait faire mieux et trouver un algorithme qui le résout plus rapidement en temps polynomial x^2, x^3 par exemple… ?
Autrement dit est-ce que P = NP ? Ou bien, est-ce que les problèmes que l’on peut vérifier de manière polynomiale peuvent être résolus de manière polynomiale ?
Il suffit de résoudre en temps polynomial un seul problème NP-Complet (c’est-à-dire de complexité maximale) pour répondre à tous les problèmes de la classe NP (et y en a un bon paquet); mais pour le moment on ne sait pas ! Intuitivement, on aurait donc tendance à penser que P ≠ NP.
Par contre, si l’on prouve l’égalité, les principaux problèmes mathématiques de ce siècle deviendraient triviaux à résoudre. Ce serait une véritable révolution… dans le séquençage d’ADN, de preuve de théorème, de factorisation, d’ordonnancement et j’en passe…
En informatique, cela pourrait compromettre toute la sécurité contemporaine des algorithmes de cryptage symétrique, asymétrique, hash. En effet, tout le principe de ces algos est essentiellement basé sur le fait qu’on puisse rapidement calculer (par exemple déchiffrer avec une clé), mais la résolution du problème sans la clé est très longue.
On a du mal à voir toutes les conséquences que ça pourrait avoir dans la vie réelle… les avancées comme les désastres qu’une telle résolution pourrait apporter.
Sources
http://fr.wikipedia.org/wiki/Probl%C3%A8me_P%3DNP
http://linuxfr.org/users/finss/journaux/p-np-demontre
https://www.youtube.com/watch?v=rkDlTQFucBM
http://rjlipton.wordpress.com
