Quel serait l'impact de P = NP? [fermé]

18

Je me prépare pour un test et je ne trouve pas de réponse claire à la question: quel serait l'impact de prouver que PTIME = NPTIME. J'ai vérifié wikipedia et il vient de mentionner que cela aurait "un impact profond sur les mathématiques, l'IA, les algorithmes .." etc.

N'importe qui peut me donner une réponse?

latusaki
la source
Cela n'a rien à voir avec le développement de logiciels. J'ai fermé pour l'instant mais j'ai demandé aux mods de Math.StackExchange s'ils voulaient que je migre cela pour vous.
maple_shaft

Réponses:

22

La première chose qui me vient à l'esprit est que la sécurité de la cryptographie à clé publique dépend actuellement de l'impossibilité de forcer les problèmes mathématiques de force brute qui sont dans la classe de difficulté NP. Si P = NP, tout ce qui dépend de PKC (y compris HTTPS, ce qui signifie que toute l'infrastructure de commerce électronique moderne et mondiale ) devrait être retravaillé!

Mason Wheeler
la source
4
Cela garantirait qu'il existe des algorithmes qui s'exécutent en temps polynomial. Ce ne serait alors qu'un compte à rebours pour trouver ces algorithmes, puis kaboom pour ainsi dire.
World Engineer
7
Une preuve impliquerait de trouver un algorithme de temps polynomial pour un problème NP-complet. Et lorsque vous trouvez un algorithme polynomial, vous pouvez l'utiliser pour résoudre tous les autres problèmes NP-complets en réduisant les problèmes à une forme commune. Cela signifie qu'une preuve pour P = NP et les algorithmes qui l'utilisent apparaîtront en même temps.
Oleksi
7
Bien sûr, les facteurs constants peuvent être si importants pour en faire un problème théorique ... pendant un certain temps.
quant_dev
17
Lorsque nous trouvons un tel algorithme, il peut encore avoir un facteur constant horriblement élevé ou être d'un degré énorme (n ^ 10000 est polynomial, mais à de nombreuses fins pratiques, il est bien pire qu'une petite complexité exponentielle). Bien sûr, ce serait un signe d'avertissement pour tout le monde de s'éloigner des anciennes méthodes, comme nous nous sommes éloignés du DES avant qu'il ne soit prouvé qu'il soit résoluble, mais l'économie mondiale ne s'effondrerait pas immédiatement. Pensez simplement à l'argent lui-même: tout le monde sait finalement que cela ne fonctionne pas à moins d'y croire, mais le commerce mondial fonctionne toujours bien.
Kilian Foth,
5
Nous aurions probablement recours à des tampons à usage unique. Amazon pourrait vous envoyer une clé USB de 1 Go qui fonctionnerait avec son site et vous maintiendrait pendant le reste de votre vie.
Macneil
18

Ceci est couvert dans L'état du problème P par rapport à NP . Vaut vraiment le détour.

Quelques points saillants de l'article (cités dans la section What If P = NP? ):

  • La cryptographie à clé publique devient impossible.
  • Puisque tous les problèmes d'optimisation NP-complets deviennent faciles, tout sera beaucoup plus efficace. Le transport de tous les formulaires sera planifié de manière optimale pour déplacer les personnes et les marchandises plus rapidement et moins cher. Les fabricants peuvent améliorer leur production pour augmenter la vitesse et créer moins de déchets.
  • L'apprentissage devient facile en utilisant le principe du rasoir d'Occam - nous trouvons simplement le plus petit programme cohérent avec les données. La reconnaissance de la vision presque parfaite, la compréhension et la traduction du langage et toutes les autres tâches d'apprentissage deviennent triviales. Nous aurons également de bien meilleures prévisions du temps et des tremblements de terre et d'autres phénomènes naturels.
  • P = NP aurait également de grandes implications en mathématiques. On pourrait trouver des preuves courtes et entièrement logiques pour les théorèmes, mais ces preuves sont généralement extrêmement longues. Mais nous pouvons utiliser le principe du rasoir Occam pour reconnaître et vérifier les preuves mathématiques telles qu'elles sont généralement écrites dans les revues. On peut alors trouver des preuves de théorèmes qui ont des preuves de longueur raisonnable disons en moins de 100 pages. Une personne qui prouve P = NP rentrerait à pied de l'Institut Clay non pas avec un chèque de 1 million de dollars mais avec sept (en fait six depuis que la conjecture de Poincaré semble résolue).
vinaykola
la source
2
Je ne vois pas comment P = NP implique que la cryptographie à clé publique est impossible. Cela suggère (mais n'implique pas) que les implémentations actuelles ne sont pas aussi difficiles à casser que nous le pensions auparavant. Mais comme d'autres l'ont souligné, si les constantes pertinentes dans un algorithme de réduction de temps optimal sont extrêmement grandes, alors P = NP n'aurait aucun impact sur la cryptographie à clé publique.
emory
+1 pour le troisième point - tout le monde sait que P = NP affecterait la cryptographie, mais pour une raison quelconque, vous entendez rarement comment cela affecterait littéralement toutes les autres disciplines informatiques de la planète.
BlueRaja - Danny Pflughoeft
@emory: Je ne prétendrai pas être un expert, mais je crois comprendre que si un tel algorithme était trouvé, même avec une constante assez élevée, nous devions repenser totalement notre approche. De plus, qui doit dire une fois qu'un algorithme est trouvé, nous ne pouvons pas en trouver un autre avec une constante plus petite? Un algorithme déverrouillerait également tous les autres problèmes NP-complets. L'effet immédiat n'est donc peut-être pas important, mais il faudrait réfléchir à changer tous les systèmes existants.
vinaykola
la première fois que j'ai entendu parler du principe du rasoir d'Occam. Choses intéressantes ...
UmNyobe
@vinaykola prouvant P = NP n'implique pas de trouver un algorithme. Bien sûr, trouver un algorithme serait le moyen le plus simple (mais pas le seul) de prouver P = NP, puis si les constantes étaient raisonnables, nous pourrions entrer dans les problèmes que vous avez soulevés.
emory
7

La plupart des problèmes NP complets ont des applications réelles "intéressantes". P=NPaura beaucoup de conséquences:

  • Il sera possible de résoudre exactement les problèmes d'optimisation qui sont actuellement approximés. C'est le cas du problème du voyageur de commerce et du problème de planification des travaux
  • Il casse certaines mesures de sécurité basées sur le fait que le temps de calcul requis est énorme. Par exemple, de nombreux schémas et algorithmes de cryptage en cryptographie sont basés sur la factorisation des nombres, l'algorithme le plus connu ayant une complexité exponentielle. Ces algorithmes deviendront inutiles si un algorithme polynomial est trouvé.

L'essentiel, c'est la nature des problèmes connus pour être NP-complets. Ce ne sont pas seulement des problèmes créés par quelques scientifiques éloignés pour se divertir les uns les autres. Ils peuvent être exprimés en termes commerciaux. En fait, certains intervieweurs d'emploi aiment cacher les problèmes NP-complets dans leurs questions afin de tester les candidats.

UmNyobe
la source
3
Bien que la factorisation entière soit un problème difficile, il convient de noter qu'elle n'est pas connue pour être NP-complète.
dan_waterworth
4
@dan_waterworth: On ne sait pas si la factorisation entière est NP-difficile, mais on sait qu'elle est en NP. [Il semble souvent que les gens disent "NP-complet" quand ils veulent dire "en NP" ou "NP-dur". D'une certaine manière, ce serait comme si quelqu'un disait "inférieur ou égal à" dans une situation où "inférieur à" serait plus précis.]
Macneil
5

Ces possibilités sont couvertes dans les cinq mondes d'Impagliazzo .

Voici quelques points à retenir:

  • L'intelligence artificielle pourrait faire un bond de géant. Par exemple, avec suffisamment de «données d'apprentissage», les circuits les plus courts pour produire les sorties correctes à partir des entrées représenteraient la meilleure méthode de traduction. En particulier, il deviendrait trivial d'avoir une parfaite reconnaissance vocale et une parfaite traduction linguistique. Prenant cette idée plus loin, si vos données d'entraînement sont des films primés aux Oscars, cela peut générer plus de films primés aux Oscars pour vous.

  • Les algorithmes enseignés dans les écoles seraient radicalement différents. Au lieu d'apprendre autant de techniques algorithmiques différentes , les cours se concentreraient sur la réduction des problèmes à la vérification des bonnes réponses. Cela simplifierait considérablement la programmation.

  • L'économie deviendrait beaucoup plus efficace. Il y aurait des perturbations, y compris le déplacement des programmeurs. La pratique de la programmation elle-même consisterait davantage à recueillir des données de formation qu'à rédiger du code. Google aurait les ressources pour exceller dans un tel monde.

  • Parce que la cryptographie à clé publique serait «hors service», Amazon devrait vous envoyer un tampon unique sur une clé USB pour effectuer des transactions sécurisées.

  • Des preuves mathématiques pourraient être générées et vérifiées automatiquement.

Globalement, cela introduirait une singularité technologique; les implications de P = NP seraient d'une grande portée. En outre, Lance Fortnow aborde ce point dans un article de blog distinct que vous devez lire.

Macneil
la source
-1

L'impact de la preuve de P = NP inclurait un regain d'intérêt pour la recherche d'un algorithme de réduction. Les gens essaieraient également de trouver des bornes inférieures sur les constantes associées à l'algorithme de réduction.

Prouver P = NP ne serait pas aussi significatif que le prétendent d'autres réponses, car il pourrait prendre la forme d'une preuve de connaissance nulle. Connaître P = NP sans connaître l'algorithme de réduction serait peu différent de la situation actuelle.

Imaginez que quelqu'un prouve que l'algorithme de réduction existe mais qu'il est O (sqrt (n) + 2 ^ 4096).

Emory
la source
1
En fait, il existe un algorithme de réduction explicite qui est dans P si et seulement si P = NP. Elle consiste à parcourir tous les programmes possibles et à les exécuter en parallèle jusqu'à ce que l'on trouve la solution.
Arthur B
@ArthurB fascinant. En supposant que P = NP, quel est l'ordre de l'algorithme?
emory
C'est inconnu, mais c'est l'ordre optimal. scholarpedia.org/article/Universal_search
Arthur B
1
@ArthurB donc si P = NP et l'algorithme de réduction est O (n ^ 99999999), P = NP est-il toujours si important?
emory