Quelles seraient les implications réelles d'une preuve constructive ?

56

J'ai une compréhension de haut niveau du problème et je comprends que s'il était absolument "avéré" d'être vrai avec une solution fournie, cela ouvrirait la porte à la résolution de nombreux problèmes du domaine de l'informatique.P=NP

Ma question est la suivante: si quelqu'un publiait une preuve constructive incontestable de , quels seraient certains des effets immédiats que nous verrions d'une telle découverte? P=NP

Je ne demande pas d'opinion sur ce que serait le monde dans 5 à 10 ans. Au lieu de cela, j’ai bien compris qu’il s’agissait d’un problème si fondamentalement insoluble qu’il pourrait changer radicalement la façon dont nous calculons ... beaucoup de choses (oui, c’est là que mon ignorance montre ...) que nous ne pouvons pas calculer facilement aujourd’hui. .

Quel type d'effet quasi immédiat une preuve complète, précise et constructive de aurait-elle sur le monde pratique?P=NP

RLH
la source
5
Dans le pire des cas, il pourrait ne pas y avoir d'effet pratique (autre que la notoriété des auteurs) - si la preuve est non constructive, ce qui signifie que quelqu'un ne fait que prouver qu'il existe. algorithmes pol-time pour les problèmes NP-complets sans en fournir réellement.
lukas.coenig
2
Ma chose préférée à considérer dans ce scénario hypothétique est le fait que l'optimisation devient facile. Un cas spécifique serait que trouver des paramètres qui sont des MLE globaux pour tout modèle probabiliste deviendrait trivial. Par exemple, cela affecterait immédiatement les chercheurs en génétique et autres sciences en leur permettant de mieux estimer les paramètres sous-jacents de leurs modèles.
Nicholas Mancuso
Il convient de mentionner ce que je pense être l'alternative la plus probable dans le scénario improbable que P = NP: à savoir qu'il est prouvé qu'aucun problème dans NP ne peut échouer dans P, mais sans aucun exemple d'algorithme P pour un NP- problème complet. Le fait que quelqu'un puisse démontrer qu'il doit exister une solution en P ne signifie pas que nous pouvons réellement trouver cette solution ni en vérifier l'exactitude. Ironiquement, cette dernière partie serait peut-être plus facile à réaliser si un algorithme P pour un problème de PNJ existait, mais bon, c'est un peu un problème de poule-à-œuf ...
Eamon Nerbonne le
5
Le bit "constructif" est un hareng rouge. Il existe un programme spécifique bien connu qui résout la SAT en temps polynomial si et seulement si (il s'agit essentiellement d'une queue d'aronde sur tous les solveurs de SAT). Ainsi, une preuve classique de s'assure déjà que ce solveur SAT particulier est dans , nous obtenons donc aussi une preuve constructive. P = N P PP=NPP=NPP
Andrej Bauer

Réponses:

34

Les gens ont donné de bonnes réponses en supposant que avec une constante très grande. Je vais jouer à l'optimiste et supposer que nous trouvons une preuve de avec une constante trop petite. Peut-être peu probable, mais je vais essayer de vous donner une idée de ce qui se passerait si nous pouvions résoudre efficacement tous problèmes de .P = N P N PP=NPP=NPNP

  • Compilateurs: Certains programmes informatiques deviendraient légèrement plus rapides, car les compilateurs utilisent la coloration graphique pour l'attribution de registres. Nous pourrions allouer exactement pour un grand nombre de registres. Les compilateurs existants utilisant une solution approximative (comme des graphiques en accords) obtiendraient un meilleur rendement et ceux utilisant une solution exacte deviendraient plus rapides.

  • Emplacement des installations: les entreprises seraient en mesure de trouver le meilleur endroit pour installer des usines et des dépôts d’approvisionnement à expédier à leurs magasins, alors qu’il existe probablement des milliers de magasins et d’usines. Ne constituerait probablement pas une amélioration considérable par rapport aux approximations modernes, mais réduirait les coûts.

  • Achat de billets d'avion: les billets d'avion sont bizarres car ils ne suivent pas l'égalité des triangles. Parfois, il est moins cher de voler de A -> B -> C que directement de A -> C, ce qui ne se produit pas lors de la modélisation des distances. Il serait facile de créer un site Web proposant la séquence de vols la moins chère possible qui se rend dans un certain nombre de villes et commence et se termine dans votre ville natale.

  • Conception de circuits: les circuits électriques sur une puce sont essentiellement des formules booléennes. Des éléments tels que la minimisation pourraient être calculés efficacement afin que notre matériel devienne un peu plus efficace.

  • Ordonnancement: vous êtes fou que votre école mette deux de vos examens au même moment? Si votre école pourrait indiquer le nombre d’intervalle de temps dont ils ont besoin pour qu’aucun élève ne soit en conflit ou donner un nombre d’intervalles de temps, minimisez le nombre de conflits.P=NP

Ceci est juste un échantillon d'applications pratiques que nous verrions si la complétude des n'était pas un obstacle. Je suis sûr que j'en ai manqué beaucoup, mais si la construction donnée avait une bonne constante, les implications seraient considérables.NP

jmite
la source
5
Citant Wikipedia sur P vs NP : If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found.Je suis conscient que cela ne fait peut-être pas référence aux applications pratiques, mais cela ressemble certainement à une surestimation si je le compare à votre réponse. De quoi parle-t-il vraiment?
Nik Kyriakides
4
@Nicholas Un peu d'hyperbole mais je peux voir le point. Pour être incroyablement inexact: Problèmes de NPmoyenne nous pouvons vérifier si une solution est correcte en temps polynomial, mais un problème de Pmoyen nous permet de trouver une solution en temps polynomial. Si NP=Pcela signifie que c'est le même effort pour vérifier si une solution est correcte ou pour trouver une solution. Cela ne tient toutefois pas compte de facteurs constants, qui font évidemment une grande différence dans la réalité.
Voo
2
Pouvez-vous mentionner les effets sur les applications cryptographiques?
ζ--
5
Si P = NP, alors les factorisations de base seraient calculables en temps polynomial (on sait que la factorisation de base est vérifiable en temps polynomial). De nombreux algorithmes cryptographiques - comme l'incroyable RSA - reposent sur la difficulté de calculer des factorisations principales. Si la "constante" susmentionnée est suffisamment petite, tous les cryptages RSA, quelle que soit leur taille, risquent de perdre instantanément tout leur sens.
user2407038
3
Vous soulignez que vous parlez de P = NP "avec une constante extrêmement petite" et assimilez cela à "nous pourrions résoudre efficacement tous les problèmes de NP". Si votre notion d'efficacité englobe de très petites constantes, le théorème de la hiérarchie temporelle rend déjà cela impossible: il existe des problèmes qui peuvent être résolus dans le temps qui ne peuvent pas être résolus dans , encore moins ou . n 99 n 2 n log nn100n99n2nlogn
David Richerby
30

Nous ne verrons pas nécessairement d'effets. Supposons que quelqu'un trouve un algorithme qui résout 3SAT sur variables en opérations de base. Vous ne pourrez pas exécuter cet algorithme sur aucune instance, car cela prend trop de temps. Ou supposons qu’elle trouve un algorithme s’exécutant dans opérations de base. Nous ne pourrons l'utiliser que sur des instances 3SAT avec une seule variable, car cela prend trop de temps pour plusieurs variables.2 100 n n 100n2100nn100

D'autre part, supposons que P NP, et que même l'hypothèse temporelle exponentielle la plus forte soit vérifiée. Ensuite, en général, 3SAT devrait être non extractible. Pourtant, les solveurs SAT semblent bien se porter sur certains problèmes.

Qu'est-ce qu'il se passe ici? Il y a plusieurs problèmes avec la question P vs. NP:

  1. Cela ne concerne que le pire des cas.
  2. C'est seulement asymptotique.
  3. Tous les délais polynomiaux sont les mêmes.

Ces problèmes font douter de sa pertinence dans le monde réel. Maintenant, il pourrait arriver qu'un algorithme très rapide soit trouvé pour 3SAT, si rapidement que même un chiffrement symétrique deviendrait fragile. Mais je considère cela hautement improbable. D'un autre côté, il est parfaitement logique que P soit différent de NP tout en considérant que la factorisation est pratique; cela casserait certains schémas de chiffrement à clé publique. C’est une situation probable qui aurait des répercussions, mais elle n’est pas liée à la question P vs NP.

La question P vs NP peut sembler naturelle du point de vue mathématique, mais sa pertinence pratique est douteuse, à mon avis. Les recherches sur la question, d’autre part, pourraient ou non avoir des répercussions pratiques; il n'est pas guidé par cet aspect.

Yuval Filmus
la source
2
Une preuve peut ne pas inclure un algorithme P pour un problème NPC, mais si cela avait pour conséquence pratique, il serait soudainement intéressant de rechercher les problèmes NP spécifiques (ou plutôt, maintenant, les problèmes P) qui ont une valeur à grande échelle et aussi. constantes traitables. Être actuellement NP-complet signifie que cela ne vaut probablement pas la peine de regarder du tout. La conséquence pratique dans le monde réel dépend donc de la manière dont P est montré P - vous espérez une preuve permettant de construire un algorithme P pour un problème NPC, et tout dépend des détails de cet algorithme.
Eamon Nerbonne le
Si vous avez 2 ^ 100n résoudre le problème pour 3SAT, je serai ravi de prendre le panneau ASIC et de menacer de déchiffrer le RSA-2048 dans juste assez de temps pour que les certificats racine de 30 ans soient une mauvaise idée.
Josué
17

Une très bonne lecture est [1], où Impagliazzo considère cinq "mondes" possibles où les relations entre les classes de complexité sont différentes. Par exemple, dans un monde appelé Algorithmica (voir Section 2.1), nous avons que (ou un autre "équivalent moral", tel que ).N P B P PP=NPNPBPP

Dans Algorithmica, pratiquement n'importe quel problème d'optimisation serait trivial. Les langages de programmation peuvent être des langages dans lesquels une espèce possède les propriétés qu'un résultat souhaité doit avoir par rapport à l'entrée, au lieu de spécifier la manière dont le calcul doit être effectué. Les ordinateurs pourraient également trouver des preuves pour n’importe quel théorème, dans le temps approximativement de la longueur de la preuve. (Cette vue est bien sûr très optimiste et dépend d’un algorithme efficace pour résoudre un problème complet de ).NP


[1] Russell Impagliazzo. Une vision personnelle de la complexité moyenne des cas. Conférence sur la complexité, 1995.

Juho
la source
Le problème de P contre NP de Steve écrit par Clay Math Institute est une autre bonne lecture plus ancienne .
Kaveh
11

Même sans P = NP, les ordinateurs actuels sont incroyablement puissants.


Edit 22 Jan 2018 J'ai maintenant découvert comment j'aurais dû "interpréter" le texte cité dans l'exemple ci-dessous. C'était ma faute, l'élément inverse devait être unique . Voici mon fichier d'entrée du 22 décembre 2014 ( addinvrig.in ) et voici le fichier d'entrée fixe d'aujourd'hui ( addinvrigFixed.in ). La ligne cruciale est: (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).La puissance des outils de raisonnement automatisés eux-mêmes me fascine toujours, même s'ils ne peuvent pas m'empêcher de mal interpréter les écrits d'autres personnes.

L'utilisation d'outils de raisonnement automatisés m'est étonnamment utile lorsque je rencontre des théorèmes cités où je ne suis pas sûr de savoir comment "interpréter" le texte :

En 1974, Karvellas [3] a étudié le semiring inverse additif et il a prouvé ce qui suit:
(Karvellas (1974), théorème 3 (ii) et théorème 7) Prenez tout semiring inverse additif (S, +, ·).
(i) Pour tout , et (ii) Si pour tout alors est additivement commutatif.( x y ) ' = x 'y = x y ' x 'y ' = x yx,yS(xy)=xy=xyxy=xy
a S SaaSSaaSS

J'ai adapté mes fichiers d'entrée prover9 pour ce théorème, et un contre-exemple du théorème cité a été immédiatement montré. Une légère modification des hypothèses a produit de nombreux théorèmes vrais similaires, ce qui rend probable que Karvellas ait réellement énoncé et prouvé un théorème correct, qui n'a été cité que de manière incorrecte ici. Googler pour la référence de ce théorème n'a donné qu'un autre article citant Karvellas encore moins précis .


Ceci est une collection incroyablement incomplète de résultats assistés par ordinateur pour des problèmes spécifiques qui sont insolubles en général si P! = NP. Peut-être cette collection montre-t-elle au moins à certains lecteurs que nous avons tous tendance à sous-estimer les pouvoirs des ordinateurs dans ce domaine. Beaucoup d'autres réponses à cette question semblent suggérer qu'il n'y aurait pas de conséquences graves si les ordinateurs pouvaient (légèrement) être meilleurs dans la résolution de problèmes insolubles. Mais les ordinateurs résistent de mieux en mieux à résoudre des problèmes insolubles (parce que cela prend pas mal de temps et d’argent), ce qui a des conséquences très réelles. Si P = NP était prouvé, alors peut-être que la conscience de ce que les ordinateurs peuvent réellement faire (même aujourd'hui) augmenterait, et que davantage de personnes utiliseraient des ordinateurs pour les aider dans de telles tâches. (PS: Je suis convaincu que P! = NP,

Thomas Klimpel
la source
7

Il existe de nombreuses opinions sur les implications réelles de P = NP. Comme on le voit dans d’autres bonnes réponses, il existe principalement deux écoles de pensée. La première est qu’un algorithme de temps-P peut être très difficile ou irréalisable à mettre en œuvre en raison «d’anomalies inattendues» associées à l’abstraction. par exemple:

  • le programme peut être trop "grand" pour coder réellement
  • il pourrait y avoir une très grande constante impliquée de telle sorte que pour toutes les instances à la portée du "calcul terrestre", elles durent encore longtemps, c'est-à-dire que l'efficacité ne fonctionne pas, sauf pour les très grandes instances. on sait que certains algorithmes entrent effectivement dans ce cas, comme l'a récemment souligné Knuth (question 15)

En général, je cherche à mettre davantage l'accent sur les algorithmes qui fonctionnent rapidement pour les problèmes dont la taille, n, est réalisable. La plupart de la littérature actuelle est consacrée à des algorithmes asymptotiquement géniaux, mais ils ne sont utiles que lorsque n dépasse la taille de l'univers.

Une étude de cas célèbre est réalisée par Impagliazzo, cité par J. dans une autre réponse. Cependant, son essai a été quelque peu extrapolé entre-temps. Voici une excellente nouvelle référence d'un expert qui aborde cette question dans une sorte de scénario futur de science-fiction, ch2 / p11. résumant

Le billet d'or: P, NP et la recherche de l'impossible par Lance Fortnow

  • "S'il s'avère que P = NP et que nous avons des algorithmes efficaces pour tous les problèmes de NP, le monde changera de façon à faire d'Internet une note de bas de page de l'histoire. Non seulement il serait impossible de décrire tous ces changements, mais aussi Les plus grandes implications des nouvelles technologies seraient impossibles à prévoir. "

  • Algorithme rapidement implémenté sur le superordinateur. Boeing passe immédiatement un contrat pour obtenir une meilleure conception d'aile pour un nouvel avion lui permettant de voler sans escale de Londres à Sydney.

  • Algorithme de recherche utilisé pour trouver un nouvel algorithme encore plus rapide, optimisant la solution P = NP originale. Se termine par le résultat de 42 millions de lignes de code inintelligible. Appelé "l'algorithme Urbana"

  • Algorithme utilisé pour trouver des traitements contre le cancer / des traitements proches du cancer sur mesure pour les individus. guérit le cancer, le sida, le diabète, mais le rhume reste un mystère

  • L'algorithme de super ordonnancement permet aux prévisionnistes "de faire des progrès incroyables en matière de prévision météorologique, avec des prévisions précises de la température, des vents, de la couverture nuageuse et des précipitations près d'un an à l'avance. Des algorithmes similaires sauvent désormais des vies en prévoyant avec précision préparer ou évacuer au besoin. "

  • Reconnaissance faciale très précise

  • L'ordinateur peut reconstruire des modèles 3D d'une scène en temps réel sous différents angles de caméra

  • Des algorithmes informatiques contrôlent les opérations de caméra pour les événements sportifs (au lieu de contrôlés par l'homme)

  • Les commentaires et les répétitions automatisés sont générés par l'algorithme, y compris des angles et des statistiques bien choisis, et générés dans n'importe quelle langue en temps réel.

  • Le baseball / sport fantastique prend une nouvelle dimension avec des simulations très précises

  • Le goût des recettes de cuisine est amélioré par l'algorithme

  • L’algorithme pourrait être utilisé pour «apprendre à peu près tout, y compris ce qui fait du bon art, de la musique populaire et des mots qui font vibrer l’âme. Rappelez-vous que P = NP signifie que ce que nous pouvons tester, nous pouvons le trouver. processus pour reconnaître la grandeur, vous pouvez à nouveau utiliser l’algorithme pour trouver rapidement cette grandeur. "

  • Politician utilise un algorithme informatique pour reconnaître les bons discours et en générer un qui corresponde aux modèles. La parole devient virale sur Internet.

  • Les gens génèrent des œuvres d'art complètes à partir d'art incomplet ou non fini, par exemple des symphonies. ils utilisent un algorithme pour générer de nouveaux enregistrements Beatles / Elvis. Nouvel art, romans, pièces de théâtre et poésie, par exemple comédie romantique avec Humphrey Bogart / Julia Roberts.

  • Amazon peut créer un roman personnalisé pour les particuliers à la demande. NBC crée une série télévisée d'action en direct créée entièrement par ordinateur

  • Réalité virtuelle simulée dans les jeux vidéo permettant toutes les actions des joueurs au lieu d’un ensemble fixe d’histoires possibles.

  • Les forces de l'ordre utilisent l'algorithme comme "un outil incroyable pour résoudre les crimes, semblant faire l'impossible pour traquer les suspects". algorithme informatique peut reconstruire des faces probables (pour les esquisses composites) en utilisant uniquement l'ADN. La police associe un suspect de meurtre à l’aide d’une recherche massive dans la base de données de photos de permis de conduire alignée sur le dessin généré (à partir de l’ADN).

Malheureusement, peu de choses que Fortnow décrit ci-dessus sont corroborées par la littérature scientifique actuelle, à l'exception peut-être d'une extrapolation imaginative des mondes Impagliazzos. il faudrait beaucoup plus pour disséquer ce point par point, mais pour résumer, tout cela semble être divertissant mais fantastique / un voeu pieux (ou peut-être que c'est son point voilé). En fait, il y a des principes scientifiques qui entrent en conflit avec beaucoup d'éléments. Et remarquez que Fortnow est un fan de sport, il développe donc une métaphore étendue dans ce domaine, mais est-ce que cela pourrait être davantage une indication de la pensée humaine dans les rainures ?

Par exemple, on sait que "l'effet papillon" implique qu'une prévision météorologique précise au-delà d'un horizon de plusieurs jours est impossible en raison d'une "dépendance sensible aux conditions initiales" (et Fortnow a ensuite admis sur son blog des critiques répétées à ce sujet. point). En outre, il existe de nombreuses preuves que les ordinateurs échouent dans des tâches hautement subjectives, telles que la génération ou l'identification d'art influent (tâche que même les experts ne réussissent pas systématiquement).

En réalité, toute la question est presque contrefactuelle ou fausse . Notez qu'une grande majorité des experts scientifiques interrogés pensent / croient, malgré le manque de preuves irréfutables jusqu'à présent, P ≠ NP. et il est naturel de le comparer à d'autres lois / restrictions / limitations connues telles que la thermodynamique (par exemple, l'impossibilité de mouvement perpétuel / énergie libre ) et des statistiques, par exemple le "théorème du non-déjeuner libre" .

L'essentiel est que même les scientifiques experts ne peuvent peut-être pas prédire exactement le résultat de P = NP. Alors peut-être que la meilleure réponse pour l'instant est d'admettre que les humains n'ont pas de bonne réponse pour le moment.

vzn
la source
1
note: les 2 écoles de pensée sont "P = NP pourrait ne pas être une grosse affaire" à "ce serait une grosse affaire" avec Fortnow représentant cette dernière position. mais en réalité, ces deux courants de pensée échappent à la prédominance de l'hypothèse / conjecture CS. en d'autres termes (comme l' a souligné Aaronson ), ce n'est pas le genre de question à laquelle on peut répondre, par exemple simplement en tant qu'équipe A contre équipe B. la prépondérance des preuves scientifiques semble indiquer que P ≠ NP ...
vzn
1
+1 pour le livre Fortnow. J'allais le suggérer moi-même. Une liste plus courte des implications (géniales) de P = NP figure dans cacm.acm.org/magazines/2009/9/… (également de Fortnow).
Fizz
7

P contre NP, techniquement contre moralement

Comme Yuval l'a dit, il est possible que P = NP soit techniquement vrai mais moralement faux. P = NP est moralement vrai (même si pas nécessairement sur le plan technique) s'il y a un rapide algorithme déterministe (disons , ou peut - être même avec de petites constantes, rien comme ) qui résout l'un des fameux problèmes NP-complets comme SAT. IIRC, Russell Impagliazzo a dit qu'il considérerait le problème P vs NP essentiellement comme réglé si quelqu'un montre SAT peut être résolu en temps.O ( n lg * n ) 2 65 536 + 2 1024 n 256 O ( n lg n )O(n2)O(nlgn)265536+21024n256O(nlgn)

Alors que se passe-t-il si P = NP est moralement vrai?

Cela nous ramène à la raison pour laquelle NP est une classe de problèmes si intéressante. L'intuition en général est que nous voulons souvent trouver des objets de taille raisonnable (formalisés en tant que taille polynomiale) qui contiennent une propriété et que la propriété est facile à vérifier (formalisée sous la forme calculable en temps polynomial). Cette catégorie de problèmes englobe presque tous les problèmes qui nous intéressent. Pour aller au-delà, vous devez penser aux interactions entre les joueurs, comme les jeux. Le nombre de problèmes naturels intéressants qui ne se trouvent pas dans le NP (ou le PH ) est très petit comparé aux problèmes naturels intéressants du NP . Si P = NP est moralementQQQvrai alors tous ces problèmes peuvent être résolus très rapidement. Juste pour donner un exemple, vous pouvez apprendre les meilleurs poids pour des modèles d’apprentissage automatique très compliqués. Vous pouvez rompre les protocoles de cryptage.

Comparaison avec le cas où P NP est moralement vrai

Par P NP est moralement vrai, je veux dire que nous ne pouvons pas résoudre le SAT (ni aucun autre problème connu du NP-complet) beaucoup plus rapidement que la force brute, ces problèmes ne peuvent donc pas être résolus dans la pratique pour des entrées générales, même assez petites. disons 100.

P NP est-il moralement vrai que nous ne pouvons pas résoudre les problèmes difficiles à résoudre dans la pratique?

Même si P NP est moralement vrai, il est toujours possible que, pour certains de ces problèmes, nous ne nous intéressions pas aux intrants généraux et au pire, mais à une classe / distribution des intrants pouvant être résolus efficacement. Par exemple, il se peut que la résolution de SAT dans le cas digne de ce nom nécessite un temps exponentiel, mais en pratique, nous pouvons déjà résoudre SAT sur de nombreuses classes intéressantes comme la vérification de logiciel, la vérification de matériel, etc. beaucoup plus rapidement.

Cela ressemble un peu à la résolution d'un problème plus simple, par exemple, si P NP est moralement vrai, on ne peut même pas approximer efficacement TSP , mais nous pouvons déjà approcher le cas particulier de TSP sur des graphes euclidiens.

Si vous savez que vous voulez résoudre un problème NP-complet, pas sur des entrées générales mais sur des entrées avec des propriétés particulières, vous n'avez pas besoin de vous soucier du problème général. Vous devez seulement résoudre le problème plus simple. Malheureusement, il est souvent difficile de déterminer le type d’intrants qui vous tient à coeur dans la pratique.

Néanmoins, les heuristiques peuvent être incroyablement performantes dans la pratique, comme nous le voyons avec la programmation SAT ou Integer ou l’apprentissage automatique. (L’ apprentissage PAC en utilisant le modèle très simple des 3-DNF est impossible si NP RP , et beaucoup d’experts pensent que RP = P).

Kaveh
la source
3

Quel type d'effet quasi immédiat une preuve complète et précise de P = NP, avec une solution fournie, sur le monde pratique?

Il y a probablement beaucoup de grandes choses qui en résulteraient, mais personne ne s'en soucierait.

Le problème est que la base de (presque) tout le cryptage moderne repose sur l'hypothèse que P n'est pas égal à NP. Le cryptage qui protège votre mot de passe lorsqu’il passe sur Internet et est sauvegardé dans des bases de données. Le cryptage qui protège les données de carte de crédit lorsqu’elles transitent sur Internet ... Le cryptage qui protège les milliards de transactions financières quotidiennes qui lient notre économie mondiale à l’organisme géant qu’il est.

Dans le meilleur des cas, P = NP signifie que cela s’arrête. Les gens recommencent à utiliser des espèces et les banques essaient d'enregistrer ces retraits sur un support déconnecté, car les transactions avec un bureau central ne sont plus fiables. Cela dure peut-être quelques mois jusqu'à ce qu'un meilleur cryptage soit mis en œuvre à l'échelle mondiale. Meilleur cas.

Dans le pire des cas, P = NP signifie que quelqu'un brise le monde. La monnaie repose sur le concept de confiance. Vous valorisez un dollar, parce que vous espérez que votre voisin vous donnera des dollars de biens ou de services. Vous estimez que votre ordinateur a 500 dollars en banque, car vous pouvez glisser votre carte et obtenir 500 dollars de biens et services ...

Et si tu ne pouvais pas croire ça? Si P = NP, quelqu'un pourrait usurper l'identité de diverses banques, gouvernements, personnes, et randomiser efficacement le montant en devise de chaque compte. Supprimer la devise dans chaque compte. Bien sûr, diverses banques ont des sauvegardes pour en rendre compte, mais depuis combien de temps leur cryptage est-il rompu? Quelles transactions ont été bonnes et lesquelles ont été imitées? C'est impossible à savoir.

Une fois que cette confiance est brisée, le chaos s'ensuit. Les avantages de pouvoir résoudre le problème du voyageur de commerce (par exemple) sont ignorés car les gens ont du mal à se nourrir.

La réalité est probablement quelque part entre les deux, mais j'espère que cela brosse un tableau assez grand de l’importance du problème.

Telastyn
la source
4
Crypto ne serait pas aussi cassé que vous semblez suggérer. Même si P = NP, vous ne pouvez pas prédire de manière déterministe les bits générés aléatoirement (par exemple, les clés). C'est pourquoi le pad ponctuel fonctionnera toujours. Les hypothèses de dureté de calcul permettent simplement de justifier l’utilisation de clés plus courtes et de schémas asymétriques.
mdxn
2
@ mdx - Cela fait un moment que je ne l'ai pas étudié en profondeur, mais cela n'a-t-il aucune importance si vous pouvez prédire les clés si vous pouvez décoder les clés rapidement et facilement?
Telastyn
Pour la crypto à clé privée, nous essayons idéalement de répartir le caractère aléatoire du message de manière à ce qu'il soit difficile de l'annuler. L'avantage, c'est que nous pouvons utiliser des clés plus courtes, gagner du temps / espace, tout en assurant une bonne sécurité. Si un attaquant peut pratiquement annuler cela, cela ne se produit pas. Si P = NP, il faudrait alors baser la sécurité sur des problèmes plus difficiles. L'inconvénient est que le cryptage et le décryptage sont également plus difficiles à calculer.
mdxn
Bien qu'un schéma de clé privée puisse toujours conserver la sécurité théorique de l'information du caractère aléatoire de la clé, un système de clé publique ne le fera pas. C'est la situation où vous pourriez extraire la clé. Encore une fois, dans le monde où P = NP, nous pouvons utiliser un problème plus difficile pour baser sa sécurité si nous en avons un. Ce serait également moins efficace.
mdxn
1
@mdx: Les pads ponctuels ne constituent pas une solution viable aux besoins du trafic Internet, car ils doivent être livrés en toute sécurité au destinataire avant de pouvoir être utilisés. Vous venez maintenant de faire reculer le problème.
Mason Wheeler
2

Une baisse massive des dépenses en équipements, en électricité et en nuage se produira. Beaucoup de choses sont actuellement calculées avec la force brute, ou des approximations qui utilisent encore un fort forçage brutal. Nous ne ferons plus tous ces calculs de force brute massivement paralysés.

Ce n’est certes pas la seule utilisation de l’informatique en nuage, mais cela restera un facteur notable sur la consommation d’énergie, le traitement en nuage, etc. Seules les économies d’énergie pourraient être remarquables sur notre empreinte carbone.

L'intelligence artificielle va aussi devenir bien meilleure. Nous pouvons enfin avoir un ordinateur qui peut être le meilleur des joueurs de GO, et votre calculatrice graphique vous battra aux échecs.

dsollen
la source
4
Notez que les problèmes de calcul associés à GO ont tendance à être complets pour les classes supérieures à NP: déterminer le gagnant dans GO généralisé à un tableau est PSPACE-complet si vous incluez la règle ko et EXPTIME-complet si vous ne le faites pas. D'une part, cela signifie que P = NP n'aide pas GO; Par contre, GO est joué sur un tableau , pas . De plus, les téléphones de la plupart des gens peuvent déjà les battre aux échecs, donc P = NP n'aura pas beaucoup d'impact pratique dans ce pays. 19 × 19 n × nn×n19×19n×n
David Richerby
Vous supposez que les problèmes que nous résolvons actuellement en forçant brutalement le PN tombent, et que tous les blessés deviennent immédiatement traitables. C'est loin d'être vrai.
Yves Daoust
0

Je ne m'attendrais pas à une révolution. Nous avons appris à vivre dans un monde où P NP et avons trouvé des solutions de contournement critiques (telles que des solutions approximatives).

Et la conjecture réfutée ne signifie pas que tous les problèmes d’utilité pratique seraient résolus en un claquement de doigts. En premier lieu, ils peuvent toujours être plus difficiles que NP.

Yves Daoust
la source
-1 parce que votre argument ne dépend d'aucun détail du système sur lequel il est censé raisonner. Par le même argument, nous avons appris à vivre dans un monde sans voitures, donc je ne m'attendais pas à ce que les voitures provoquent une révolution. À l'inverse, nous avons appris à vivre dans un monde sans chaussures au format MP3, donc je ne m'attendrais pas à ce qu'ils provoquent une révolution. L'un de ces exemples est clairement faux, l'autre probablement vrai. Votre conclusion à propos de P vs NP pourrait être l'une ou l'autre.
David Richerby
@DavidRicherby: merci d'avoir expliqué le vote négatif.
Yves Daoust