Welcher war der erste Roman, der in Universen mit P=NP spielt?

Ich frage mich, ob jemand einen Roman geschrieben hat, der in einem Universum P=NPspielt, in dem, falls es mehr als eines gibt, welches das erste war?

Geben Sie hier die Bildbeschreibung ein

In diesem Universum könnten alle Probleme, die in polynomieller Zeit (NP) verifiziert werden könnten (bei gegebener Lösung), auch in polynomieller Zeit (P) gelöst werden.

aus gutem Grund, würde ich mir vorstellen. Ich kann den Dialog gerade sehen.
Greg Egan schrieb Dark Integers und Luminous, in denen es um Berechenbarkeit und Komplexität in einer reinen Algebra-Umgebung geht. Wenn das funktionieren kann, kann das auch ein Roman über P=NP :)
Die MathFiction-Homepage wäre ein guter Ausgangspunkt für so etwas.
Kein Roman, aber Russell Impagliazzo (ein Top-Forscher für Komplexitätstheorie) hat einen kurzen Artikel geschrieben, in dem er fünf Welten beschreibt, in denen solche Dinge passieren (das Algorithmica-Universum hat P = NP, Cryptomania hat eine garantierte Public-Key-Kryptographie usw.). Ich dachte nur, ich würde es erwähnen, falls Sie neugierig auf einen theoretischeren Standpunkt sind, wie eine Welt mit P = NP aussehen würde. blog.computationalcomplexity.org/2004/06/…
Dr. G +1, aber ich bin mir nicht sicher, welche Versionen von Egans Kurzgeschichten Sie gelesen haben: P, aber ich nahm an, dass sich die Wahrheitswerte arithmetischer Aussagen wie der Spin eines Quantenteilchens verhalten und die Berechnung mathematisch Das Ergebnis war, diese Wahrheitswerte zu Lasten eines „anderen, parallelen Universums“ umzukehren. Die Physik selbst war von der Änderung der mathematischen Regeln betroffen, so dass überall Chaos herrschte, als die „Anderen“ zurückschlugen. (Und ja, ich habe einen Doktortitel in reiner Mathematik)
...und woher wissen Sie, dass P=NP nicht wahr ist, unser Universum? Lass es mich wissen und ich teile die 1 Million Dollar mit dir.
@DavidRoberts Ich hätte die Frage als Roman formulieren sollen, der in einem Universum spielt, in dem wir P = NP kennen :) Re: Egan, ich habe die Geschichte als eine Wendung der intensionalen Definition interpretiert. Unsere Theorie basiert auf einer intensionalen Definition, was nicht bedeutet, dass das Universum zustimmt, und da wir nicht versucht haben, die Erweiterungsversion unserer Definitionen zu verifizieren, könnte das physikalische Universum anderer Meinung sein.
Vielleicht alle von ihnen ... Da es im Moment ein ungelöstes Problem ist. :-)
Können Sie ganz einfach erklären, was P=NP bedeutet und woher wir wissen, ob ein Buch, das wir gerade lesen, in diesem Universum zu finden ist?
@Wikis: In einem P = NP-Universum wäre das Finden einer korrekten Lösung für eine große und gut definierte Hierarchie von Problemen nur so komplex wie das Erkennen , dass eine vorgeschlagene Lösung für ein solches Problem korrekt ist. Zum Beispiel scheint es in unserem Universum viel einfacher zu sein, zu erkennen, dass ein Kunstwerk großartig ist, als ein großartiges Werk zu schaffen. In einem Universum mit P = NP wäre der erforderliche Aufwand gleich oder nur geringfügig größer, wenn man ihn in Bezug auf die Größe des zu lösenden Problems betrachtet. Das einfache Knacken fast aller Verschlüsselungsformen ist ein weiteres Zeichen für ein P=NP-Universum.
@DrG: Greg Egan könnte wahrscheinlich einen Roman schreiben, in dem P und NP die Protagonisten sind. Dieser Typ lässt Kim Stanley Robinson wie George Lucas aussehen.

Antworten (10)

Star Trek, Various, 1966 (frühestes Vorkommen)

P=NP im Star Trek-Universum, aber die Leute dort wissen es nicht. Beweis:

  1. Es gibt eine Verschlüsselung, aber sie ist immer knackbar. Mit P=NP können Sie alles außer Einmal-Pads knacken, aber die Federation verwendet hartnäckig weiterhin NP-basierte Chiffren.

  2. Die Wirksamkeit des Universalübersetzers. P=NP würde das Erlernen neuer Sprachen zum Kinderspiel machen, zumindest für einen Computer. Lernsysteme wären so einfach und unkompliziert zu implementieren, dass kein Linguist mehr einen Job hätte.

  3. Die Wirksamkeit des Biofilters. Der Transporter filtert routinemäßig unbekannte Organismen, Viren und andere Gefahren, wenn Besatzungsmitglieder an Bord des Schiffes gebeamt werden. Aber „Biofilter“ ist ein irreführender Begriff, da er an eine Art Sieb erinnert, das alles Schlechte auffängt und nur das Gute durchlässt. In Wirklichkeit wäre das Ausführen eines solchen "Filters" über Transportdaten die Mutter aller induzierten Subgraph-Isomorphie-Probleme , da Sie alle virusgroßen Strukturen in einem Organismus voller solcher Strukturen identifizieren müssten. P=NP zaubert den eingabebezogenen Exponenten weg, der solche Probleme selbst für kleine Graphen unlösbar macht.

  4. Selbstbewusste Maschinenintelligenz wird mit Leichtigkeit erstellt. Wesley Crusher hat aus Versehen eine erstellt. So auch Richard Daystrom. Der Enterprise-D-Computer kochte Moriarty in seinen Ersatzzyklen, Dr. Farallon erschuf die Exocomps und so weiter. Alles, was Sie anscheinend tun müssen, ist, etwas zu bauen, das einem Theorem-Beweissystem entspricht, und es lange genug laufen lassen, um über den Beweis zu stolpern, dass P oder eine andere handhabbare Klasse äquivalent zu NP ist und das System ins Rennen geht.

Oder vielleicht stürzen die Star-Trek-Bewohner die Polynom-Hierarchie mit technologischen Mitteln ein. Die Föderation, Borg usw. scheinen leichten Zugang zu Zeitmaschinen, Wurmlöchern, exotischer Materie und superluminalen Signalen zu haben, sodass sie geschlossene zeitähnliche Kurven für Berechnungen verwenden könnten. Laut Scott Aaronson würde dies es ihnen ermöglichen, PSPACE-vollständige Probleme effizient zu lösen.

+1 für die Verwendung von Beweisen aus der Welt, um etwas zu zeigen. Allerbeste.
Ich denke, sie gehen lediglich die drei Punkte an, die Sie mit roher Rechenleistung ansprechen. Ein DTM kann genau die gleichen Probleme lösen wie ein NTM, dauert aber länger. Wenn ihre technischen Fähigkeiten also verrückt genug sind, können sie wirklich schnelle (parallele) Computer aushusten (außerdem haben sie wahrscheinlich ein paar nette Heuristiken für einige NP-schwere Probleme auf dem Weg gefunden). Also, ich bin mir nicht sicher, wie Ihre Argumente gelten.
@Blue Vielleicht hätte ich schreiben sollen, dass P = NP Sie alles Nützliche außer Einmal-Pads knacken lässt. Wenn Sie die Entschlüsselung nicht in polynomieller Zeit verifizieren können, was ein Kryptosystem außerhalb von NP bedeutet, dann ist selbst mit der Schlüsselentschlüsselung rechnerisch nicht durchführbar. Das ist für mich kein nützliches Kryptosystem.
@bitmask: Irgendwo in den technischen Handbüchern steht, dass Star Trek den Computerkern in einem modifizierten Warp-Feld betreibt, in dem die Zeit mit einer anderen Geschwindigkeit läuft.
@MichaelEdenfield: Wenn es Problemlösungstechniken gibt, die streng genommen leistungsfähiger sind als ein sehr schnelles DTM, und für praktische Anwendungen P und NP an Relevanz verloren haben, ist das an sich schon ein sehr starker Beweis für P = NP im Universum. In einem P!=NP-Universum ist die Entdeckung solcher Techniken sehr unwahrscheinlich.
@Tynam P und NP sind streng im Hinblick darauf definiert, was mit deterministischen und nicht deterministischen Turnig-Maschinen möglich ist. es macht einfach keinen Sinn, außerhalb dieses Zusammenhangs darüber zu sprechen. Es gibt bereits Hinweise darauf, dass Quantencomputer beispielsweise eine Möglichkeit bieten könnten , nicht-deterministische Berechnungen durchzuführen ...
@MichaelEdenfield: Guter Punkt; Ich hatte den Quantencomputer / NDTM-Winkel nicht durchdacht. Allerdings scheint der praktische Unterschied zwischen einem P=NP-Universum und einem deutlich leistungsfähigeren ND-Computing-Universum wahrscheinlich gering zu sein. (Aber ich bin nicht davon überzeugt, dass das menschliche Gehirn wesentlich leistungsfähiger ist als ein DTM; Parallelität ist nicht dasselbe wie algorithmische Komplexität.)
Könnten Sie das mit einem Datum versehen?
@AncientSwordRage Datum auf was?
@Kyle das Datum, an dem Sie glauben, dass die Star Trek-Serie erstmals als P = NP dargestellt wurde.
@AncientSwordRage Wenn ich aus meinen Beispielen wähle, müsste es die erste Episode sein, in der der Universalübersetzer in einer Erstkontaktsituation verwendet wird. In TOS wäre das Episode 10 der ersten Staffel, „The Corbomite Maneuver“, als Enterprise auf Baalok und den Spaßball der First Federation traf.
@kyle, das macht es 1966, was ein Anwärter ist. Wären Sie dagegen, dass ich es in Ihre Antwort einarbeite?
@AncientSwordRage nein, mach weiter.

Antikörper, Charles Stross, 2000

Eine Kurzgeschichte, die davon abhängt, dass das Lösen von P=NP eine notwendige Voraussetzung für die Entwicklung einer Computerintelligenz ist. Es ist in seinem Buch Toast verfügbar . Stross hat den vollständigen Text dieses Buches online gestellt. ( Dieser Link führt Sie direkt zur Geschichte.)

Und laut Stross 'Website lautete die Geschichte:

Veröffentlicht in Interzone Nr. 157; neu veröffentlicht in "The Year's Best Science Fiction # 18" (Hrsg. Gardner Dozois). Erwähnt in Locus' „Recommended Reading List“ für 2000. In die engere Wahl für den Theodore Sturgeon Award 2001 (verloren an Ian MacDonalds „Tendoleo's Story“).

Das andere Stross-Buch, das sich damit befasst, ist The Atrocity Archives , wo Alan Turing P=NP löste, aber sie stellten dann fest, dass dies den Zugang zu den Cthonic Realms ermöglichte, sodass jetzt ein ganzer Zweig der Regierung existiert, um zu verhindern, dass diese Entdeckung öffentlich bekannt wird .

In Vernor Vinges „Zones of Thought“-Reihe („The Blabber“, „ A Fire Upon the Deep “ , „ A Deepness in the Sky “ und „ The Children of the Sky “ ) ist die Berechnung in manchen Teilen der Galaxie einfacher, was Dinge ermöglicht wie Künstliche Intelligenz und FTL-Reisen.

Es wurde spekuliert (aber es gibt keine direkten Beweise in den Büchern), dass P=NPin diesen Zonen.

Gibt es indirekte Beweise? Meine Erinnerung ist, dass die Berechnung außerhalb der langsamen Zone anders ist (die These von Church gilt nur in der langsamen Zone) und so etwas wie P = NP muss dort nicht gelten oder sogar Sinn machen.
In A Fire Upon the Deep finden die Skode Riders Phams Glauben an die Verschlüsselung mit öffentlichen Schlüsseln humorvoll. Daraus können wir das P == NPim Jenseits schließen.
Nicht unbedingt – Quantencomputer könnten theoretisch NP-vollständige Probleme in polynomieller Zeit bewältigen, auch ohne P=NP.
Nein sie können nicht. Die Operationen, auf deren Schwierigkeit die am weitesten verbreiteten Public-Key-Verschlüsselungsalgorithmen angewiesen sind – Factoring, Discrete Log – sind (angeblich) nicht NP-vollständig. Das sind die Probleme, die Quantencomputer theoretisch in polynomieller Zeit lösen können. Davon abgesehen gibt es Public-Key-Verschlüsselungsalgorithmen, die auf NP-vollständigen Problemen basieren, aber diese sind (noch ...) nicht weit verbreitet.
@BlueRaja Wir kennen derzeit keine Möglichkeit, einen Quantencomputer zu verwenden, um NP-vollständige Probleme effizient zu lösen, aber Sie behaupten, das P < NP <= BQPsei falsch, und mir ist kein Beweis dafür bekannt. Ich stimme zu, dass es wahrscheinlich falsch ist, aber Sie geben es als Tatsache an.
@Code: Ja, tut mir leid, dass ich nicht sorgfältig gesprochen habe. Ich meinte, es ist nicht bekannt (oder geglaubt), dass es theoretisch möglich ist.
Ich wollte Denkzonen sagen. Ich bin mir nicht sicher, ob P = NP buchstäblich wahr ist, da es möglich ist, dass an einem bestimmten Ort in einer Zone unsere Intuition, dass Sie ein NP-Problem konstruieren können, das Sie nicht einfach lösen können, zutrifft. Aber ich denke, es ist ähnlich genug, um erwähnt zu werden, da Sie sich in eine höhere Zone bewegen (oder eine Nachricht senden) können, wo Ihr Problem leicht lösbar ist.

In der Fanfic Harry Potter and the Methods of Rationality von Eliezer S. Yudkowsky bekommt Harry eine Zeitmaschine und versucht, das Produkt zweier großer Primzahlen mit dieser Maschine zu faktorisieren, mit einem etwas seltsamen Ergebnis. Das ist also nicht ganz gegeben NP=P, scheint aber wahrscheinlich.

Das macht keinen Sinn. Ein Problem gehört in P, wenn es eine bestimmte Turingmaschine gibt, die dieses Problem löst (Definition von NP ist ähnlich). Es spielt keine Rolle, ob es andere denkbare Mittel gibt, um dieses Problem zu lösen. Durch das Hacken von Zeitschleifen kam Harry über die P=NP-Frage hinaus.
Ja, wenn sein Test erfolgreich war, hätte das bedeutet, dass es ein „stärkeres“ Rechengerät als die Turing-Maschine gibt, und damit widerlegte er Churchs These. Wenn Sie also NP mit Turing-Maschinen definiert lassen, würde dies nicht beweisen, dass 'NP = P' ist.
IIRC, es wurde bewiesen, dass P = PSPACE (was stärker ist als P = NP) für eine Turing-Maschine, die mit der Fähigkeit ausgestattet ist, Daten zeitlich rückwärts zu senden, selbst wenn sie der Novikov-Selbstkonsistenz unterliegt. Es ist immer noch möglich, dass P = PSPACE für gewöhnliche Turing-Maschinen gilt, aber dies wird von „Mainstream“-Komplexitätstheoretikern als noch weniger plausibel als P = NP angesehen.

The Roaring Trumpet von Spague de Camp und Fletcher Pratt, veröffentlicht im Mai 1940 in Unknown. Hier postulieren Psychologen, dass Schizophrene tatsächlich mental auf alternative Universen zugreifen, und durch Anwendung der richtigen Gleichungen könnte man in dieses alternative Universum reisen und den Geist der Person zurück in unser Universum bringen. Es war eine intellektuelle Übung, die der Hauptprotagonist Harold Shea zu testen beschließt. Er bezieht sich scherzhaft auf das Reisen per Syllogismobil, aber es beinhaltet, die Logik des Ziels des Universums zu studieren und zu konstruieren und sie laut zu rezitieren. Dies beginnt im Allgemeinen mit "wenn P gleich nicht P ist ..." und geht von dort aus. Die gesamte Enchanter-Serie lässt sie dabei durch Mythologie und Märchen und klassische Werke hüpfen.

Ich vermute, ohne wirklich darüber nachgedacht zu haben, dass sie das Universum als eines unterschieden, in dem Magie funktioniert, indem sie P = NP voranstellten.

„NP“ in „P = NP“ bedeutet jedoch nicht „nicht P“. Die Formulierung könnte auf einem Missverständnis beruhen, aber ich bin sicher, dass das Problem P vs. NP bis 1940 nicht formuliert wurde, also wollten sie wahrscheinlich nur einen Widerspruch behaupten ("P" ist ein allgemeiner Satz; indem angenommen wird, dass P und nicht P , alles kann folgen.) AFAIK Die Frage P gegen NP wurde erstmals 1971 als solche gestellt.

Nemesis, Isaac Asimov, 1989

Es spricht über Unmöglichkeiten und die Implikationen eines Universums, in dem die Gesetze der Physik nicht gelten

Bitte gib beim nächsten Mal bei deiner Antwort ein Datum an und erkläre, warum sich das explizit auf P=NP bezieht.

Der Übungseffekt , David Brin, 1984

Dies scheint ein wahrscheinlicher Kandidat zu sein. Im abgebildeten Universum beginnt eine Robotersonde aus unserem Universum, sich sowohl körperlich als auch geistig selbst zu optimieren, während die menschliche Intelligenz unverändert bleibt. Auch physische Objekte neigen zur Selbstoptimierung: Ein Holzschlitten entwickelt Schmiermittel, um problemlos auf der Straße zu gleiten. Dieser Übungseffekt kann durch einen speziellen Trancezustand verstärkt werden, in dem die Lösung sofort von selbst erscheint, daher führen unbelebte Objekte eine weitreichende Evolution innerhalb einer nicht-polynomiellen Zeit durch (Suche nach einer nahezu unendlichen Reihe möglicher Lösungen innerhalb eines kurzen Zeitraums). . Dieses Universum transzendiert tatsächlich P=NP.

Bitte bearbeiten Sie, warum Sie denken, dass dies der Fall ist.

In der Geschichte Starshield Sentinels von Margaret Weis und Tracy Hickman gab es Computer/künstliche Intelligenzen, die jede Frage sofort beantworten konnten, indem sie die Frage in der Zeit an sich selbst zurückschickten und ihm „Zeit“ gaben, sie zu lösen. Der einzige Haken dabei war, dass der Computer lange genug „wach“ sein musste, um es zu lösen (etwas wie Deep Thought aus The Hitchhiker's Guide to the Galaxy, das 10 Millionen Jahre brauchte, um die Frage nach dem Leben, dem Universum und allem zu lösen).

Obwohl ich nicht weiß, ob dies genau alles P = NP betrifft, löst es die Variablen- / Solve-Klausel in der Frage.

Natürlich drehen die Computer alle durch und versuchen, jeden in der Geschichte zu töten. Können wir nicht jetzt aufhören, Killerroboter zu erfinden?

Wenn ich mich nicht irre, verbringt in Bob Shaws „ The Ragged Astronauts “ eine der Figuren ein wenig Zeit damit, einer anderen zu erklären, wie Pi gleich 3 ist. Wenn Pi 3 ist, kann ich mir nur vorstellen, wie der Rest der Physik aussieht. (Ich erinnere mich überhaupt nur an die Szene, weil die ganze Szene etwas fehl am Platz war, was ziemlich ungewöhnlich für das Buch war - ansonsten war es eine nette Geschichte).

Wie hängt das mit p=np zusammen?
Welcher war der erste Roman, der in Universen mit P=NP spielt?
AntwortenHierDatenschutz-Bestimmungen1y, 0v