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

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$

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 $P=NP$$P=NP$$NP$

• 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$

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 $n$$2^{100} n$$n^{100}$

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.$\neq$

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.

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 $\sf P = NP$$\sf NP \subseteq BPP$

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 ).$\sf NP$

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

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

• 128738912746470189375617083569165010477776126539149096721635802187 peut être pris en compte par un seul ordinateur en moins d'une seconde.
• Pour les tâches plus difficiles telles que la synthèse de la structure électrique d'une puce à partir d'une description plus détaillée de ses fonctions ou la correction de photomasques pour compenser les artefacts du processus de fabrication, des grappes de plusieurs centaines d'ordinateurs travaillent toute la journée pour permettre l'impossible.
• Les ordinateurs actuels sont capables de prouver des théorèmes mathématiques qu'aucun humain n'a pu prouver, comme si les algèbres de Robins étaient booléennes, ou qu'une certaine constante supposée non liée ( problème de divergence d'Erdős ) était supérieure à 2.
• Les programmes d’analyse de code source statique sont en mesure d’identifier des vulnérabilités telles que le bogue Heartbleed .
• Les outils de raisonnement automatisés tels que prover9 ou le prouveur de théorème E sont capables de prouver la plupart des caractérisations algébriques courantes des semi-groupes inverses et des anneaux fortement réguliers sans aucune aide explicite.

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 ⋅ $x, y \in S$$(x \cdot y)' = x' \cdot y = x \cdot y'$$x' \cdot y' = x \cdot y$
a ∈ S $a \in aS \cap Sa$$a \in S$$S$

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,

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.

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(n^2)$$O(n^{\lg^* n})$$2^{65536}+2^{1024}n^{256}$$O(n^{\lg n})$

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 moralement$Q$$Q$vrai 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$\neq$

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.$\neq$

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

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.$\neq$

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.$\neq$

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).$\neq$

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.

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.

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).$\ne$

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.