|
| Agrandir |
| Si les problèmes P et NP se résolvent de manière différente, sont-ils distincts pour autant ? © images |
Ce troisième défi est peut-être le plus accessible car il ne nécessite pas un bagage mathématique trop imposant. Il s'agit d'un problème qui concerne les ordinateurs, plus exactement, leur efficacité à résoudre certaines tâches.
Il existe plusieurs types de problèmes. Les E, qui nécessiteraient des millions d'années de calculs pour être résolus, les P, exécutables par un ordinateur, et les NP, intermédiaires. Ces NP problèmes sont les plus fréquents, notamment dans l'industrie et pour la planification de tâches.
La nature des problèmes
Qu'est-ce qui distingue les problèmes P des NP ?
Un problème P se décompose en un algorithme, une suite de calculs élémentaires. Par exemple, additionner 2 nombres à 4 chiffres requiert 12 étapes élémentaires. Evidemment, plus le nombre de chiffres augmente, plus le nombre d'étapes augmente. On parle d'augmentation à temps polynomial. Pour des données de taille N, il nécessite au plus N*C^k opérations élémentaires avec C et k fixés. Les ordinateurs peuvent mener à bien ces opérations.
Maintenant, prenons un exemple simple, celui du voyageur de commerce. Il doit couvrir 3 villes selon un trajet minimum. Pour cela il doit étudier chaque itinéraire possible puis définir le plus court. Facile, cela offre 6 chemins différents. Mais avec 10 villes, il y en a 3 628 800. Et avec 25, plus de 10 ^26 ! C'est énorme et à ce jour, personne ne connaît de méthode pratique pour ce type de problème.
On parle de problème NP, processus polynomial mais non déterministe. Seul le nombre élevé de possibilités pose problème. Un ordinateur capable de faire des choix pourrait vérifier qu'une solution donnée convient en un temps polynomial. C'est le cas de la factorisation d'un entier en produit de facteurs premiers. On ne sait pas s'il existe un algorithme polynomial qui réussisse cette opération. Autrement dit, on ne sait pas si ce problème est dans P. En revanche, étant donné des nombres a, b, c
, on peut facilement vérifier si ce problème est dans NP.
A-t-on P=NP ? Autrement dit, peut-on trouver en temps polynomial ce que l'on peut prouver en temps polynomial?
