p versus NP problem, dans le problème polynomial complet versus polynomial non déterministe, dans la complexité informatique (un sous-domaine de l’informatique théorique et des mathématiques), la question de savoir si tous les soi-disant problèmes NP sont en fait des problèmes P. Un P problème peut être résolu en « temps polynomial, ce qui signifie qu’un algorithme existe pour sa solution, tels que le nombre d’étapes de l’algorithme est bornée par une fonction polynomiale de n, où n correspond à la longueur de l’entrée du problème., Ainsi, les problèmes P sont dits faciles, ou traitables. Un problème est appelé NP si sa solution peut être devinée et vérifiée en temps polynomial, et non déterministe signifie qu’aucune règle particulière n’est suivie pour faire la supposition.

Les problèmes de programmation linéaire sont NP, car le nombre d’étapes de la méthode simplex, inventée en 1947 par le mathématicien américain George Dantzig, croît exponentiellement avec la taille de l’entrée. Cependant, en 1979, le mathématicien russe Leonid Khachian a découvert un algorithme en temps polynomial—c’est-à-dire,, le nombre d’étapes de calcul augmente comme une puissance du nombre de variables, plutôt que de façon exponentielle—montrant ainsi que les problèmes de programmation linéaire sont en fait P. Cette découverte a permis la solution de problèmes autrefois insolubles.

Un problème est NP-difficile si un algorithme pour sa solution peut être modifié pour résoudre tout problème NP—ou tout P problème, pour cette question, que P est une sous-ensemble de problèmes NP. (Cependant, tous les problèmes NP-hard ne sont pas membres de la classe des problèmes NP.) Un problème à la fois NP et NP-dur est dit NP-complet., Ainsi, trouver un algorithme efficace pour tout problème NP-complet implique qu’un algorithme efficace peut être trouvé pour tous les problèmes NP, car une solution pour tout problème appartenant à cette classe peut être refondue en une solution pour tout autre membre de la classe., En 1971, L’informaticien américain Stephen Cook a prouvé que le problème de satisfiabilité (un problème d’attribution de valeurs à des variables dans une formule en algèbre booléenne telle que l’énoncé est vrai) est NP-complet, ce qui a été le premier problème démontré comme NP-complet et a ouvert la voie à montrer d’autres problèmes qui sont membres de Un exemple célèbre de problème NP-complet est le problème du vendeur itinérant, qui a de larges applications dans l’optimisation des horaires de transport., On ne sait pas si des algorithmes de temps polynomial seront jamais trouvés pour les problèmes NP-complets, et déterminer si ces problèmes sont traçables ou insolubles reste l’une des questions les plus importantes en informatique théorique. Une telle découverte prouverait que P = NP = NP-complète et révolutionne de nombreux domaines de l’informatique et des mathématiques.

Par exemple, la cryptographie moderne repose sur l’hypothèse que l’affacturage, le produit de deux grands nombres premiers n’est pas P., Notez que Vérifier le produit de deux nombres premiers est facile (temps polynomial), mais calculer les deux facteurs premiers est difficile. La découverte d’un algorithme efficace pour factoriser de grands nombres briserait la plupart des schémas de cryptage modernes.

en 2000, le mathématicien américain Stephen Smale a élaboré une liste influente de 18 problèmes mathématiques importants à résoudre au 21e siècle. Le troisième problème sur sa liste était le problème P contre NP., Toujours en 2000, il a été désigné un problème du Millénaire, l’un des sept problèmes mathématiques sélectionnés par le Clay Mathematics Institute de Cambridge, Massachusetts, États-Unis, pour un prix spécial. La solution pour chaque problème du Millénaire vaut 1 million de dollars.