Question:
Quel était le premier roman dans des univers où P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

Je me demande si quelqu'un a écrit un roman dans un univers où P = NP , au cas où il y en aurait plus d'un, lequel était le premier?

enter image description here

Dans cet univers, tous les problèmes qui pourraient être vérifiés en temps polynomial (NP) (étant donné la solution) pourraient également être résolus en temps polynomial (P).

pour une bonne raison, j'imagine. Je peux voir le dialogue maintenant.
Greg Egan a écrit des entiers sombres et lumineux qui traitent de la calculabilité et de la complexité dans des paramètres d'algèbre pure. Si cela peut fonctionner, un roman sur P = NP peut l'être également :)
Pas un roman, mais Russell Impagliazzo (un chercheur de haut niveau en théorie de la complexité) a écrit un court article décrivant cinq mondes dans lesquels de telles choses se produisent (l'univers Algorithmica a P = NP, Cryptomania a garanti la cryptographie à clé publique, etc.). Je pensais juste que je le mentionnerais au cas où vous seriez curieux d'avoir un point de vue plus théorique sur ce à quoi ressemblerait un monde avec P = NP. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr G +1, mais je ne sais pas quelles versions des nouvelles d'Egan vous avez lues: P mais j'ai pris cela comme étant que les valeurs de vérité des déclarations arithmétiques se comportaient comme le spin d'une particule quantique, et le calcul des mathématiques les résultats renversaient ces valeurs de vérité, au détriment d'un «autre univers parallèle». La physique elle-même a été affectée par le changement des règles mathématiques, il y avait donc un chaos généralisé lorsque les «autres» ont riposté. (Et oui, j'ai un doctorat en mathématiques pures)
... et comment savez-vous que P = NP n'est pas vrai dans notre univers? Faites-le moi savoir et je partagerai le million de dollars avec vous.
@DavidRoberts J'aurais dû formuler la question comme un roman se déroulant dans un univers où nous connaissons P = NP :) Re: Egan, j'ai interprété l'histoire comme une torsion de la définition intensionnelle. Notre théorie est basée sur une définition intensionelle, ne signifie pas que l'univers est d'accord, et puisque nous n'avons pas essayé de vérifier la version extensionnelle de nos définitions, l'univers physique pourrait être en désaccord.
Peut-être tous ... Puisqu'il s'agit d'un problème non résolu en ce moment. :-)
La [page d'accueil de MathFiction] (http://kasmana.people.cofc.edu/MATHFICT/) serait un bon point de départ pour quelque chose comme ça.
Pouvez-vous expliquer, en termes * vraiment * simples, ce que signifie P = NP et comment nous saurions si un livre que nous lisons serait dans cet univers?
@Wikis: Dans un univers P = NP _finding_ une solution correcte à une grande hiérarchie bien définie de problèmes serait aussi complexe que _reconnaissant_ qu'une solution proposée à un tel problème est correcte. Par exemple, dans notre univers, reconnaître qu'une œuvre d'art est grande semble être beaucoup plus facile que de créer une grande œuvre. Dans un univers où P = NP, la quantité d'effort requis serait la même ou seulement légèrement supérieure si on la considérait en termes de taille du problème à résoudre. Le craquage facile de presque toutes les formes de cryptage est un autre signe d'un univers P = NP.
@DrG: Greg Egan pourrait probablement écrire un roman où P et NP sont les protagonistes. Ce type fait ressembler Kim Stanley Robinson à George Lucas.
Dix réponses:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

Star Trek, Various, 1966 (première occurrence)

P = NP dans l'univers de Star Trek, mais les gens là-bas ne le savent pas. Evidence:

  1. Il y a un cryptage mais il est toujours cassable. P = NP vous permettra de tout déchiffrer sauf des tampons ponctuels, mais la Fédération continue obstinément d'utiliser des chiffrements basés sur NP.

  2. L'efficacité du traducteur universel. P = NP faciliterait l'apprentissage de nouvelles langues, du moins pour un ordinateur. Les systèmes d'apprentissage seraient si simples et simples à mettre en œuvre qu'il ne resterait plus de linguiste avec un travail.

  3. L'efficacité du bio-filtre. Le transporteur filtre régulièrement les organismes inconnus, les virus et autres dangers lorsque les membres d'équipage sont téléportés à bord du navire. Mais "bio-filtre" est un terme trompeur car il évoque une sorte de tamis qui capte toutes les mauvaises choses et ne passe que les bonnes. En réalité, exécuter un tel "filtre" sur les données de transport serait la mère de tous les problèmes d'isomorphisme de sous-graphes induits, car vous auriez à identifier toutes les structures de la taille d'un virus dans un organisme regorgeant de telles structures. P = NP élimine l'exposant lié à l'entrée qui rend ces problèmes insolubles même pour les petits graphiques.

  4. L'intelligence artificielle consciente de soi est créée facilement. Wesley Crusher en a créé un par accident. Tout comme Richard Daystrom. L'ordinateur Enterprise D a préparé Moriarty dans ses cycles de réserve, le Dr Farallon a créé les Exocomps, et ainsi de suite. Tout ce que vous semblez avoir à faire est de construire quelque chose d'équivalent à un système de démonstration de théorème et de le laisser courir assez longtemps pour trébucher sur la preuve que P ou une autre classe traitable est équivalent à NP et que le système est hors course. >

Ou peut-être que les habitants de Star Trek réduisent la hiérarchie polynomiale par des moyens technologiques. La Fédération, Borg, etc. semblent avoir facilement accès aux machines à voyager dans le temps, aux trous de ver, à la matière exotique et à la signalisation superluminale, de sorte qu'ils pourraient utiliser des courbes de type temps fermées pour le calcul. Cela selon Scott Aaronson leur permettrait de résoudre efficacement les problèmes complets de PSPACE.

+1 pour avoir utilisé des preuves du monde pour montrer quelque chose. Très excellent.
Je pense qu'ils abordent simplement les trois points que vous émettez par la puissance de calcul brute. Un DTM peut résoudre exactement les mêmes problèmes qu'un NTM, mais cela prend plus de temps. Donc, si leurs compétences en ingénierie sont assez folles, ils peuvent cracher des ordinateurs très rapides (parallèles) (ils ont également probablement trouvé quelques heuristiques intéressantes pour certains problèmes NP-difficiles en cours de route). Donc, je ne sais pas comment vos arguments s'appliquent.
@Blue J'aurais peut-être dû écrire P = NP vous permet de tout casser, mais des pads ponctuels. Si vous ne pouvez pas vérifier le décryptage en temps polynomial, ce qui signifie avoir un cryptosystème en dehors de NP, alors le décryptage _e même avec la clé_ n'est pas réalisable sur le plan informatique. Ce n'est pas pour moi un cryptosystème utile.
@bitmask: C'est quelque part dans les manuels techniques que Star Trek exécute le cœur de l'ordinateur dans un champ de distorsion modifié où le temps s'écoule à un rythme différent.
@MichaelEdenfield: S'il existe * des * techniques de résolution de problèmes strictement plus puissantes qu'un DTM très rapide, et que pour des applications pratiques P et NP ont perdu de leur pertinence, cela en soi est une preuve très forte de P = NP dans l'univers. Dans un univers P! = NP, la découverte de telles techniques est très improbable.
@Tynam P et NP sont définis strictement en termes de ce qu'il est possible de faire avec des machines Turnig déterministes et non déterministes; cela n'a tout simplement aucun sens d'en parler en dehors de ce contexte. Il existe déjà des preuves que les ordinateurs quantiques * pourraient * fournir un moyen d'effectuer des calculs non déterministes, par exemple ...
@MichaelEdenfield: Bon point; Je n'avais pas réfléchi à l'angle ordinateur quantique / NDTM. Cela dit, la différence pratique entre un univers P = NP et un univers de calcul ND significativement plus puissant semble probablement minime (mais alors, je ne suis pas convaincu que le cerveau humain est significativement plus puissant qu'un DTM; le parallélisme n'est pas la même chose que la complexité algorithmique.)
Pourriez-vous mettre une date à cela?
AiliwcihshCMT Date à quoi?
@Kyle la date à laquelle vous pensez que la série Star Trek a été décrite pour la première fois comme P = NP.
@AncientSwordRage En choisissant parmi mes exemples, je pense que ce devrait être le premier épisode mettant en vedette l'utilisation du traducteur universel dans une situation de premier contact.Dans TOS ce serait l'épisode 10 de la première saison, "The Corbomite Manoeuvre" quand * Enterprise * a rencontré Baalok et la balle amusante de la Première Fédération.
@kyle qui en fait 1966, qui est un prétendant.Seriez-vous opposé à ce que je le modifie dans votre réponse?
@AncientSwordRage non, allez-y.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

Anticorps, Charles Stross, 2000

Une histoire courte qui repose sur le fait que la résolution de P = NP est une condition préalable nécessaire pour développer une intelligence informatique. Il est disponible dans son livre Toast . Stross a mis en ligne le texte intégral de ce livre. ( Ce lien vous mènera directement à l'histoire.)

Et selon le site de Stross, l'histoire était:

Publié dans Interzone # 157; republié dans "The Year's Best Science Fiction # 18" (éd. Gardner Dozois). Mentionné dans la "Liste de lectures recommandées" de Locus pour 2000. Sélectionné pour le prix Theodore Sturgeon 2001 (perdu contre "L'histoire de Tendoleo" d'Ian MacDonald).

#3
+25
deworde
2011-09-26 04:42:50 UTC
view on stackexchange narkive permalink

L'autre livre Stross qui traite de cela est The Atrocity Archives, où Alan Turing a résolu P = NP, mais ils ont ensuite constaté que cela permettait d'accéder aux royaumes Cthonic, donc maintenant une branche entière du gouvernement existe pour empêcher cette découverte de devenir publique.

#4
+18
Mike Scott
2011-01-13 13:20:03 UTC
view on stackexchange narkive permalink

Dans la série «Zones of Thought» de Vernor Vinges («The Blabber», A Fire Upon the Deep , A Deepness in the Sky et le prochain The Children of the Sky ), le calcul est plus facile dans certaines parties de la galaxie, permettant des choses comme l'intelligence artificielle et les voyages FTL.

Il a été spéculé (mais il n'y a aucune preuve directe dans les livres) que P = NP dans ces zones.

Y a-t-il des preuves indirectes? Je me souviens que le calcul est différent en dehors de la zone lente (la thèse de Church ne vaut que dans la zone lente) et quelque chose comme P = NP n'a pas besoin de s'appliquer ou même d'avoir un sens là-bas.
Dans * A Fire Upon the Deep *, les Skode Riders trouvent que la croyance de Pham dans le cryptage à clé publique est humoristique. De cela, nous pouvons conclure que «P == NP» dans l'Au-delà.
Pas nécessairement - les ordinateurs quantiques pourraient théoriquement gérer des problèmes NP-complets en temps polynomial, même sans P = NP.
Non ils ne peuvent pas. Les opérations sur lesquelles les algorithmes de chiffrement à clé publique les plus répandus reposent sur la difficulté - factorisation, journalisation discrète - ne sont pas (considérées comme) NP-complètes. Tels sont les problèmes que les ordinateurs quantiques sont théoriquement capables de casser en temps polynomial. Cela étant dit, il existe des algorithmes de cryptage à clé publique qui * sont * basés sur des problèmes NP-complets, mais ceux-ci ne sont pas largement utilisés (encore ...)
@BlueRaja Nous ne connaissons actuellement aucun moyen d'utiliser un ordinateur quantique pour résoudre efficacement des problèmes NP complets, mais vous affirmez que `P
@Code: Oui, désolé, je n'ai pas parlé attentivement. Je voulais dire que ce n'est * pas * connu (ou cru) théoriquement possible.
J'allais dire Zones de pensée. Je ne suis pas sûr qu'il soit littéralement vrai que P = NP, dans la mesure où il est possible que _à n'importe quel endroit particulier d'une zone_, notre intuition que vous pouvez construire un problème NP que vous ne pouvez pas résoudre facilement soit vraie. Mais je pense que c'est assez similaire pour qu'il soit intéressant de le mentionner, en ce sens que vous pouvez vous déplacer (ou envoyer un message) vers une zone plus élevée, où votre problème sera facilement résolu.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

Dans la fanfic Harry Potter et les méthodes de rationalité d'Eliezer S. Yudkowsky, Harry obtient une machine à remonter le temps et essaie de factoriser le produit de deux grands nombres premiers en utilisant cette machine, avec un résultat un peu bizarre. Donc ce n'est pas complètement donné que NP = P , mais semble probable.

Cela n'a pas de sens. Un problème appartient à P, si une certaine machine de Turing résolvant ce problème existe (la définition de NP est similaire). Peu importe qu'il existe d'autres moyens envisageables pour résoudre ce problème. En piratant les boucles temporelles, Harry a dépassé la question P = NP.
Oui, si son test avait réussi, cela aurait signifié qu'il existe un dispositif de calcul «plus puissant» que la machine de Turing et il a donc réfuté la thèse de Church. Donc, si vous laissez NP défini à l'aide de machines de Turing, cela ne prouverait pas «NP = P».
IIRC, il a été prouvé que P = PSPACE (qui est plus fort que P = NP) pour une machine de Turing équipée de la capacité d'envoyer des données en arrière dans le temps, même si elle est soumise à l'auto-cohérence Novikov.Il est toujours possible que P = PSPACE pour les machines de Turing ordinaires, mais cela est considéré comme encore moins plausible que P = NP par les théoriciens de la complexité «grand public».
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

The Roaring Trumpet de Spague de Camp et Fletcher Pratt, publié en mai 1940 dans Unknown. Ici, les psychologues postulent que les schizophrènes accèdent en fait mentalement à des univers alternatifs et qu'en appliquant les équations appropriées, on pourrait voyager dans cet univers alternatif et ramener l'esprit des personnes dans notre univers. C'était un exercice intellectuel que le principal protagoniste Harold Shea décide de tester. Il fait référence en plaisantant au voyage via syllogismobile, mais cela implique d'étudier et de construire la logique de la destination de l'univers et de la réciter à haute voix. Cela commence généralement par "si P est égal à non P ..." Et va de là. Toute la série Enchanter leur fait parcourir l'univers de la mythologie, des contes de fées et des œuvres classiques.

Je soupçonne, sans jamais y avoir vraiment réfléchi, qu'en faisant précéder de P = NP, ils distinguaient le univers comme celui dans lequel la magie fonctionne.

#7
+1
Gelvis
2011-01-13 22:16:51 UTC
view on stackexchange narkive permalink

Nemesis, Isaac Asimov, 1989

Il parle des impossibilités et des implications d'un univers où les lois de la physique ne s'appliquent pas

Veuillez fournir une date avec votre réponse, la prochaine fois et expliquer pourquoi cela se rapporte * explicitement * à P = NP.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

L'effet d'entraînement , David Brin, 1984

Cela semble un candidat probable. Dans l'univers représenté, une sonde robotique de notre univers commence à s'auto-optimiser à la fois physiquement et mentalement tandis que l'intelligence humaine reste inchangée. Les objets physiques ont également tendance à s'auto-optimiser: un traîneau en bois développe du lubrifiant pour glisser facilement sur la route. Cet effet de pratique peut être amplifié par un état de transe spécial où la solution apparaît immédiatement par elle-même, par conséquent, les objets inanimés effectuent une évolution à large plage dans un temps non polynomial (recherche d'un tableau presque infini de solutions possibles dans un court laps de temps) . Cet univers transcende en fait P = NP.

Veuillez [modifier] pourquoi vous pensez que c'est le cas.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

Dans l'histoire Starshield Sentinels de Margaret Weis et Tracy Hickman, il y avait des ordinateurs / intelligences artificielles qui pouvaient répondre à n'importe quelle question instantanément en renvoyant la question dans le temps. , en lui donnant «le temps» de le résoudre. Le seul hic à cela était que l'ordinateur devait être `` éveillé '' assez longtemps pour le résoudre (quelque chose comme Deep Thought du Guide de l'auto-stoppeur de la galaxie ayant besoin de 10 millions d'années pour résoudre la question de la vie, de l'univers et de tout).

Bien que je ne sache pas si cela concerne exactement tout P = NP, cela résout la clause variable / résoudre dans la question.

Bien sûr, tous les ordinateurs deviennent fous et essaient de tuer tout le monde dans l'histoire. Ne pouvons-nous pas arrêter d'essayer d'inventer des robots tueurs maintenant?

#10
-2
Michael Kohne
2011-09-27 06:38:38 UTC
view on stackexchange narkive permalink

Si je ne me trompe pas, dans « The Ragged Astronauts» de Bob Shaw, l'un des personnages passe un peu de temps à expliquer comment pi vaut 3 à un autre. Si pi vaut 3, je ne peux qu'imaginer à quoi ressemble le reste de la physique. (Je ne me souviens pas du tout de la scène parce que toute la scène était un peu déplacée, ce qui était assez inhabituel pour le livre - sinon c'était une belle histoire).

Comment cela se rapporte-t-il à p = np?


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 2.0 sous laquelle il est distribué.
Loading...