Que se passerait-il si P était égal à NP ?

De nombreux problèmes actuellement considérés comme insolubles, de la planification optimale à la rupture des codes cryptographiques, disposeraient d'algorithmes efficaces, et l'acte de trouver des solutions ne serait pas plus difficile que de les vérifier. Les effets sur le commerce, la sécurité et la science seraient profonds, ce qui explique en partie pourquoi la plupart des experts s'attendent à ce que P ne soit pas égal à NP.

Pourquoi le problème est-il si difficile à résoudre ?

Prouver que P est égal à NP nécessite un algorithme rapide pour un problème NP-complet, ce que personne n'a trouvé ; prouver qu'ils sont différents nécessite de montrer qu'un tel algorithme ne peut pas exister. Les résultats sur la relativisation et les preuves naturelles démontrent que les techniques standard sont intrinsèquement incapables d'établir ce dernier point, de sorte qu'une approche véritablement nouvelle est nécessaire.

Le problème P versus NP

Le problème P versus NP pose la question de savoir si tout problème dont les solutions peuvent être vérifiées rapidement peut également être résolu rapidement ; il s'agit de la question ouverte centrale de l'informatique théorique et de l'un des problèmes du Prix du Millénaire de Clay.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

P est la classe des problèmes résolubles en temps polynomial, et NP la classe des problèmes dont les solutions proposées sont vérifiables en temps polynomial ; le problème P versus NP demande si ces deux classes sont égales, ce qui est vrai si et seulement si un problème NP-complet quelconque est résoluble en temps polynomial.

Scope

Ce sujet aborde l'énoncé formel de P versus NP, son équivalence avec la question de savoir si un problème NP-complet quelconque possède un algorithme en temps polynomial, les conséquences de chaque réponse possible, les obstacles tels que la relativisation, les preuves naturelles et l'algébrisation qui ont entravé les progrès, ainsi que la conjecture largement répandue selon laquelle les classes sont différentes.

Core questions

Trouver une solution est-il fondamentalement plus difficile que de la vérifier ?
Pourquoi la réponse dépend-elle du fait qu'un problème NP-complet quelconque appartienne à P ?
À quoi ressemblerait le monde si P était égal à NP, et s'il ne l'était pas ?
Pourquoi des décennies d'efforts n'ont-elles pas permis de résoudre la question ?

Key theories

Équivalence à la NP-complétude: P est égal à NP si et seulement si tout problème NP-complet possède un algorithme en temps polynomial ; ainsi, la question générale se réduit à la traitabilité d'un seul problème concret tel que la satisfiabilité.
Barrières de preuve: Les résultats sur la relativisation, les preuves naturelles et l'algébrisation montrent que les principales techniques de preuve connues ne peuvent pas résoudre P versus NP, ce qui explique la difficulté et guide la recherche de méthodes fondamentalement nouvelles.

Clinical relevance

L'inégalité présumée de P et NP est l'hypothèse de travail qui sous-tend le traitement des problèmes NP-difficiles comme étant insolubles et la sécurité de la cryptographie, car une résolution efficace des problèmes NP briserait les chiffrements largement utilisés ; une preuve constructive que P est égal à NP transformerait l'optimisation, la logistique et la science.

History

Cook a formulé la question en 1971, parallèlement à la NP-complétude, et elle a été rapidement reconnue comme fondamentale. Les tentatives via les bornes inférieures de circuits dans les années 1980 ont rencontré la barrière des preuves naturelles identifiée par Razborov et Rudich, et en 2000, le Clay Mathematics Institute l'a désigné comme un problème du Prix du Millénaire, assorti d'une récompense d'un million de dollars.

Debates

Le problème P versus NP sera-t-il un jour résolu, et quelle est la réponse ?: La plupart des chercheurs conjecturent que P n'est pas égal à NP, mais aucune preuve n'existe et les techniques connues sont prouvées insuffisantes. Les opinions divergent quant à savoir si une résolution est proche, si elle nécessite des mathématiques radicalement nouvelles, ou si la question pourrait même être indépendante des axiomes standards.

Key figures

Stephen Cook
Leonid Levin
Richard Karp
Alexander Razborov

Seminal works

cook1971
aroraBarak2009

Frequently asked questions

Que se passerait-il si P était égal à NP ?: De nombreux problèmes actuellement considérés comme insolubles, de la planification optimale à la rupture des codes cryptographiques, disposeraient d'algorithmes efficaces, et l'acte de trouver des solutions ne serait pas plus difficile que de les vérifier. Les effets sur le commerce, la sécurité et la science seraient profonds, ce qui explique en partie pourquoi la plupart des experts s'attendent à ce que P ne soit pas égal à NP.
Pourquoi le problème est-il si difficile à résoudre ?: Prouver que P est égal à NP nécessite un algorithme rapide pour un problème NP-complet, ce que personne n'a trouvé ; prouver qu'ils sont différents nécessite de montrer qu'un tel algorithme ne peut pas exister. Les résultats sur la relativisation et les preuves naturelles démontrent que les techniques standard sont intrinsèquement incapables d'établir ce dernier point, de sorte qu'une approche véritablement nouvelle est nécessaire.