Problème P=NP
Article mis en ligne le 23 octobre 2012 par C GIBERT
Imprimer cet article logo imprimer

Voici le plus « simple », qui s’il est résolu, pourrait entrainer la résolution des autres, donc 7 M$ !

(Ps : si vous trouvez la solution, venez l’apporter à vos profs de maths bien-aimés, ils sauront quoi en faire…quoi que 7 n’est pas divisible par 6…)

Le problème P = NP

Ce 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 ?

Dans les années 60, les chercheurs pensaient que P et NP étaient des classes différentes. Mais sans preuve. En 1971, Cook, un mathématicien américain, démontre l’existence d’un problème NP qui, s’il est soluble par une procédure à temps polynomial, prouverait que tous les NP sont des P.

Les enjeux concernent essentiellement la sécurité sur Internet. En effet, le système RSA qui permet le cryptage des messages électroniques dépend du fait que le décryptage du code ne soit pas un problème P. Si on démontrait que s’en était un, la sécurité du système serait compromise. C’est une énigme qui nécessite une bonne idée inédite, et qui pourrait être résolue par un non matheux. Alors bonne chance !

Dans la même rubrique :

Identification

Calendrier

septembre 2017
lunmarmerjeuvensamdim
28293031123
45678910
11121314151617
18192021222324
2526272829301
Évènements à venir
Pas d'évènements à venir

Articles les plus vus

Statistiques du site

  • Nombre total de visites :
    175700 visiteurs
  • Aujourd'hui :
    38 visiteurs
  • Nombre de pages visitées :
    237372 pages
  • Actuellement en ligne :
    8 visiteurs
  • Ce site contient :
    179 articles
  • Dernier article paru :
    "Liste des manuels, rentrée 2016"
    le 11 septembre 2017
puce Contact puce Espace rédacteurs puce squelette puce RSS puce Valid XHTML 1.0 Strict
Site réalisé sous SPIP
avec le squelette ESCAL-V2
Version : 2.6.7 [61555]