Vraag:
Wat was de eerste roman die zich afspeelt in universums waar P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

Ik vraag me af of iemand een roman heeft geschreven die zich afspeelt in een universum waarin P = NP , in het geval dat er meer dan één is, welke de eerste was?

enter image description here

In dit universum zouden alle problemen die konden worden geverifieerd in polynoomtijd (NP) (gegeven de oplossing) ook kunnen worden opgelost in polynoomtijd (P).

om een ​​goede reden, zou ik me voorstellen. Ik kan de dialoog nu zien.
Greg Egan schreef Dark integers en Luminous die gaan over berekenbaarheid en complexiteit in een pure algebra-omgeving. Als dat kan werken, kan ook een roman over P = NP :)
Geen roman, maar Russell Impagliazzo (een toponderzoeker op het gebied van complexiteitstheorie) schreef een korte paper waarin hij vijf werelden beschrijft waarin dergelijke dingen gebeuren (het Algorithmica-universum heeft P = NP, Cryptomania heeft cryptografie met openbare sleutels gegarandeerd, enz.). Ik dacht dat ik het zou vermelden voor het geval je nieuwsgierig bent naar een meer theoretisch standpunt over hoe een wereld met P = NP eruit zou zien. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr. G +1, maar ik weet niet zeker welke versies van Egan's korte verhalen je hebt gelezen: P maar ik nam aan dat waarheidswaarden van rekenkundige uitspraken zich gedroegen als de spin van een kwantumdeeltje, en de berekening van wiskundige resultaten waren het omdraaien van deze waarheidswaarden, ten nadele van een 'ander, parallel universum'. De natuurkunde zelf werd beïnvloed door het veranderen van de regels van de wiskunde, dus er was overal chaos toen de 'anderen' terug vochten. (En ja, ik heb een doctoraat in zuivere wiskunde)
... en hoe weet je dat P = NP niet waar is in ons universum? Laat het me weten en ik deel de $ 1 miljoen met je.
@DavidRoberts Ik had de vraag moeten formuleren als een roman die zich afspeelt in een universum waar we P = NP kennen :) Re: Egan, ik interpreteerde het verhaal als een draai aan de intensionele definitie. Onze theorie is gebaseerd op een intensieve definitie, wat niet betekent dat het universum het daarmee eens is, en aangezien we niet hebben geprobeerd om de extensionele versie van onze definities te verifiëren, is het fysieke universum het daar misschien niet mee eens.
Misschien allemaal ... Omdat het op dit moment een onopgelost probleem is. :-)
De [MathFiction Homepage] (http://kasmana.people.cofc.edu/MATHFICT/) zou een goed startpunt zijn voor zoiets.
Kun je in * echt * eenvoudige bewoordingen uitleggen wat P = NP betekent en hoe we zouden weten of een boek dat we lezen in dat universum zou zijn?
@Wikis: In een P = NP-universum _finding_ een juiste oplossing voor een grote en goed gedefinieerde hiërarchie van problemen zou slechts zo complex zijn als het _herkennen_ dat een voorgestelde oplossing voor een dergelijk probleem juist is. In ons universum lijkt het bijvoorbeeld veel gemakkelijker om te erkennen dat een kunstwerk geweldig is dan het maken van een geweldig werk. In een universum waar P = NP, zou de vereiste hoeveelheid inspanning hetzelfde zijn of slechts bescheiden groter als we kijken naar de omvang van het op te lossen probleem. Het gemakkelijk kraken van bijna alle vormen van versleuteling is een ander teken van een P = NP-universum.
@DrG: Greg Egan zou waarschijnlijk een roman kunnen schrijven waarin P en NP de hoofdrolspelers zijn. Die kerel laat Kim Stanley Robinson op George Lucas lijken.
Tien antwoorden:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

Star Trek, Various, 1966 (eerste keer)

P = NP in het Star Trek-universum, maar de mensen daar zijn zich er niet van bewust. Bewijs:

  1. Er is codering maar deze is altijd breekbaar. Met P = NP kun je alles kraken behalve eenmalige blokken, maar de Federatie blijft koppig doorgaan met het gebruik van op NP gebaseerde cijfers.

  2. De doeltreffendheid van de universele vertaler. P = NP zou het leren van nieuwe talen een fluitje van een cent maken, althans voor een computer. Leersystemen zouden zo eenvoudig en ongecompliceerd kunnen worden geïmplementeerd dat er geen linguïst meer met een baan overblijft.

  3. De doeltreffendheid van het biofilter. De transporteur filtert routinematig onbekende organismen, virussen en andere gevaren wanneer bemanningsleden aan boord worden gestraald. Maar "biofilter" is een misleidende term omdat het doet denken aan een soort zeef die al het slechte materiaal opvangt en alleen het goede doorlaat. In werkelijkheid zou het uitvoeren van een dergelijk "filter" over transportgegevens de moeder zijn van alle geïnduceerde subgraafisomorfismeproblemen, aangezien je alle structuren van virusgrootte in een organisme boordevol dergelijke structuren zou moeten identificeren. P = NP goochelt de input-gerelateerde exponent weg die dergelijke problemen zelfs voor kleine grafieken moeilijk maakt.

  4. Zelfbewuste machine-intelligentie wordt met gemak gecreëerd. Wesley Crusher heeft er per ongeluk een gemaakt. Richard Daystrom ook. De Enterprise D-computer kookte Moriarty in zijn reservecycli, Dr. Farallon creëerde de Exocomps, enzovoort. Het enige wat je lijkt te hoeven doen is iets te bouwen dat gelijkwaardig is aan een stelling-beproevingssysteem en het lang genoeg laten lopen om over het bewijs te struikelen dat P of een andere handelbare klasse gelijk is aan NP en dat het systeem op weg is naar de races.

Of misschien doen de Star Trek-bewoners de polynoomhiërarchie met technologische middelen aan het instorten. De Federatie, Borg, enz. Lijken gemakkelijke toegang te hebben tot tijdmachines, wormgaten, exotische materie en superluminale signalering, dus zouden ze gesloten tijdachtige curven kunnen gebruiken voor berekeningen. Dit volgens Scott Aaronson zou hen in staat stellen om PSPACE-complete problemen efficiënt op te lossen.

+1 voor het gebruik van bewijs uit de wereld om iets te laten zien. Meest uitstekend.
Ik denk dat ze de drie punten die u oproept alleen maar aanpakken door middel van onbewerkte rekenkracht. Een DTM kan precies dezelfde problemen oplossen als een NTM, maar het duurt langer. Dus als hun technische vaardigheden gek genoeg zijn, kunnen ze hele snelle (parallelle) computers ophoesten (ze hebben waarschijnlijk ook een paar mooie heuristieken gevonden voor sommige NP-harde problemen onderweg). Dus ik weet niet zeker hoe uw argumenten van toepassing zijn.
@Blue Misschien had ik P = NP moeten schrijven, zodat je alles kunt kraken, behalve eenmalige pads. Als u de decodering in polynomiale tijd niet kunt verifiëren, wat het hebben van een cryptosysteem buiten NP betekent, dan is decodering _ zelfs met de sleutel_ niet rekenkundig haalbaar. Dat is voor mij geen handig cryptosysteem.
@bitmask: Het is ergens in de technische handleidingen dat Star Trek de computerkern binnen een aangepast warp-veld laat draaien waar de tijd met een ander tempo loopt.
@MichaelEdenfield: Als er * zijn * probleemoplossende technieken die strikt krachtiger zijn dan een zeer snelle DTM, en voor praktische toepassingen P en NP aan relevantie hebben verloren, is dat op zichzelf een zeer sterk bewijs voor P = NP in het universum. In een P! = NP-universum is de ontdekking van dergelijke technieken zeer onwaarschijnlijk.
@Tynam P en NP worden strikt gedefinieerd in termen van wat mogelijk is met deterministische en niet-deterministische Turnig-machines; het heeft gewoon geen zin om er buiten die context over te praten. Er zijn al aanwijzingen dat kwantumcomputers * een manier kunnen bieden om niet-deterministische berekeningen uit te voeren, bijvoorbeeld ...
@MichaelEdenfield: Goed punt; Ik had niet nagedacht over de kwantumcomputer / NDTM-hoek. Dat gezegd hebbende, lijkt het praktische verschil tussen een P = NP-universum en een aanzienlijk krachtiger ND-computeruniversum waarschijnlijk klein te zijn. (Maar ik ben er niet van overtuigd dat het menselijk brein veel krachtiger is dan een DTM; parallellisme is niet hetzelfde als algoritmische complexiteit.)
Kunt u hier een datum voor vastleggen?
@AncientSwordRage Datum tot wat?
@Kyle de datum waarop je denkt dat hun star trek-serie voor het eerst werd afgebeeld als P = NP.
@AncientSwordRage Als ik uit mijn voorbeelden kies, denk ik dat het de eerste aflevering zou moeten zijn waarin de universele vertaler in een eerste contact situatie wordt gebruikt.In TOS zou dat aflevering 10 zijn van het eerste seizoen, "The Corbomite Manoeuvre" toen * Enterprise * Baalok en de First Federation lolbal ontmoette.
@kyle waardoor het 1966 is, wat een kanshebber is.Zou je er tegen zijn als ik het in je antwoord verwerk?
@AncientSwordRage nee, ga je gang.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

Antibodies, Charles Stross, 2000

Een kort verhaal dat afhangt van het feit dat het oplossen van P = NP een vereiste voorwaarde is voor het ontwikkelen van computerintelligentie. Het is beschikbaar in zijn boek Toast . Stross heeft de volledige tekst van dit boek online gezet. ( Deze link brengt je rechtstreeks naar het verhaal.)

En volgens de site van Stross was het verhaal:

Gepubliceerd in Interzone # 157; heruitgegeven in "The Year's Best Science Fiction # 18" (ed. Gardner Dozois). Vermeld in Locus '"Aanbevolen literatuurlijst" voor 2000. Op de shortlist voor de Theodore Sturgeon Award 2001 (verloren door Ian MacDonald's "Tendoleo's Story").

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

Het andere Stross-boek dat hiermee te maken heeft, is The Atrocity Archives, waar Alan Turing P = NP oploste, maar toen ontdekten ze dat dit toegang gaf tot de Cthonic Realms, dus nu een hele tak of Government bestaat om te voorkomen dat deze ontdekking algemeen bekend wordt.

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

In Vernor Vinges "Zones of Thought" -serie ("The Blabber", A Fire Upon the Deep , A Deepness in the Sky en de aanstaande The Children of the Sky ), is berekeningen eenvoudiger in sommige delen van de melkweg, waardoor zaken als kunstmatige intelligentie en FTL-reizen mogelijk zijn.

Er is gespeculeerd (maar er is geen direct bewijs in de boeken) dat P = NP in deze zones.

Is er indirect bewijs? Ik herinner me dat berekeningen buiten de Slow Zone anders zijn (de stelling van de kerk geldt alleen in de Slow Zone) en zoiets als P = NP hoeft daar niet van toepassing te zijn of zelfs maar zinvol te zijn.
In * A Fire Upon the Deep * vinden de Skode Riders Pham's geloof in public key encryptie humoristisch. Daaruit kunnen we concluderen dat `P == NP` in the Beyond.
Niet per se - kwantumcomputers zouden theoretisch NP-complete problemen in polynoomtijd aankunnen, zelfs zonder P = NP.
Nee, zij kunnen niet. De bewerkingen waarvan de meest wijdverspreide coderingsalgoritmen met openbare sleutels afhankelijk zijn, zijn moeilijk - factoring, discrete log - zijn niet (verondersteld) NP-compleet te zijn. Dit zijn de problemen die kwantumcomputers in theorie kunnen doorbreken in polynoomtijd. Dat gezegd hebbende, er zijn coderingsalgoritmen met openbare sleutels die * zijn * gebaseerd op NP-complete problemen, maar deze worden (nog ...) niet algemeen gebruikt
@BlueRaja We weten momenteel geen manier om een ​​kwantumcomputer te gebruiken om NP complete problemen efficiënt op te lossen, maar u beweert dat `P
@Code: Ja, sorry, ik heb niet zorgvuldig gesproken. Ik bedoelde dat het * niet * bekend (of geloofd) is dat het theoretisch mogelijk is.
Ik wilde Zones of Thought zeggen. Ik weet niet zeker of het letterlijk waar is dat P = NP, in die zin dat het mogelijk is dat _op een bepaalde locatie in een zone_, onze intuïtie dat je een NP-probleem kunt construeren dat je niet gemakkelijk kunt oplossen, waar is. Maar ik denk dat het vergelijkbaar genoeg is om het vermelden waard te zijn, in die zin dat je naar een hogere zone kunt gaan (of een bericht kunt sturen), waar je probleem gemakkelijk kan worden opgelost.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

In de fanfic Harry Potter and the Methods of Rationality door Eliezer S. Yudkowsky krijgt Harry een tijdmachine en probeert hij het product van twee grote priemgetallen te ontbinden met deze machine, met een ietwat raar resultaat. Het is dus niet helemaal gegeven dat NP = P , maar lijkt waarschijnlijk.

Dat slaat nergens op. Een probleem hoort thuis in P, als een bepaalde Turing-machine dit probleem oplost (definitie van NP is vergelijkbaar). Het maakt niet uit of er andere manieren zijn om dit probleem op te lossen. Door tijdlussen te hacken kwam Harry verder dan de P = NP-vraag.
Ja, als zijn test succesvol was geweest, zou dat hebben betekend dat er een 'sterker' rekenapparaat is dan de Turing-machine en daarom weerlegde hij de stelling van Church. Dus als je NP gedefinieerd laat met behulp van Turing-machines, zou het niet 'NP = P' bewijzen.
IIRC, het is bewezen dat P = PSPACE (wat sterker is dan P = NP) voor een Turing-machine die is uitgerust met de mogelijkheid om gegevens in de tijd terug te sturen, zelfs als deze onderhevig is aan Novikov-zelfconsistentie.Het is nog steeds mogelijk dat P = PSPACE voor gewone Turing-machines, maar dit wordt door 'reguliere' complexiteitstheoretici nog minder aannemelijk geacht dan P = NP.
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

The Roaring Trumpet door Spague de Camp en Fletcher Pratt, gepubliceerd in mei 1940 in Unknown. Hier stellen psychologen dat schizofrenen in feite mentaal toegang hebben tot alternatieve universums, en door de juiste vergelijkingen toe te passen, zou men naar dat alternatieve universum kunnen reizen en de geest van de persoon terugbrengen naar ons universum. Het was een intellectuele oefening die de hoofdpersoon Harold Shea besluit uit te testen. Hij verwijst gekscherend naar reizen via syllogismobiel, maar het omvat het bestuderen en construeren van de logica van de bestemming van het universum en het hardop reciteren ervan. Dit begint meestal met "als P gelijk is aan niet P ..." en gaat vanaf daar verder. Door de hele Enchanter-serie huppelen ze door mythologie en sprookjesachtige en klassieke werken.

Ik vermoed, dat ik er nooit echt over nagedacht heb, dat ze, door te beginnen met P = NP, de universum als een waarin magie functioneert.

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

Nemesis, Isaac Asimov, 1989

Het gaat over onmogelijkheden en de implicaties van een universum waar de wetten van de fysica niet van toepassing zijn

Geef de volgende keer een datum bij uw antwoord en leg uit waarom dit * expliciet * betrekking heeft op P = NP.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

The practice effect , David Brin, 1984

Dit lijkt een waarschijnlijke kandidaat. In het afgebeelde universum begint een robotsonde uit ons universum zichzelf zowel fysiek als mentaal te optimaliseren, terwijl de menselijke intelligentie ongewijzigd blijft. Ook fysieke objecten hebben de neiging zichzelf te optimaliseren: een houten slee ontwikkelt smeermiddel om gemakkelijk over de weg te glijden. Dit oefeneffect kan worden versterkt door een speciale staat van trance waarin de oplossing onmiddellijk vanzelf verschijnt, daarom voeren levenloze objecten een brede evolutie uit binnen niet-polynomiale tijd (op zoek naar een bijna oneindige reeks mogelijke oplossingen binnen een korte tijdsperiode) . Dit universum overstijgt eigenlijk P = NP.

Gelieve [bewerk] in waarom u denkt dat dit het geval is.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

In het verhaal Starshield Sentinels door Margaret Weis en Tracy Hickman waren er computers / kunstmatige intelligenties die elke vraag onmiddellijk konden beantwoorden door de vraag terug in de tijd naar zichzelf te sturen , het 'tijd' geven om het op te lossen. Het enige probleem hierbij was dat de computer lang genoeg 'wakker' moest zijn om het op te lossen (zoiets als Deep Thought uit The Hitchhiker's Guide to the Galaxy heeft 10 miljoen jaar nodig om de vraag over het leven, het universum en alles op te lossen).

Hoewel ik niet weet of dit precies betrekking heeft op alles P = NP, lost het wel de variabele / oplossingsclausule in de vraag op.

Natuurlijk worden de computers allemaal gek en proberen ze iedereen in het verhaal te vermoorden. Kunnen we niet stoppen met het proberen om moordende robots uit te vinden?

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

Als ik me niet vergis, in Bob Shaw's ' The Ragged Astronauts', besteedt een van de personages een beetje tijd aan het uitleggen hoe pi 3 is voor een ander. Als pi 3 is, kan ik me alleen maar voorstellen hoe de rest van de fysica eruit ziet. (Ik herinner me de scène helemaal niet omdat de hele scène een beetje misplaatst was, wat vrij ongebruikelijk was voor het boek - anders was het een leuk verhaal).

Hoe verhoudt dit zich tot p = np?


Deze Q&A is automatisch vertaald vanuit de Engelse taal.De originele inhoud is beschikbaar op stackexchange, waarvoor we bedanken voor de cc by-sa 2.0-licentie waaronder het wordt gedistribueerd.
Loading...