Küsimus:
Milline oli esimene romaan universumites, kus P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

Huvitav, kas keegi on kirjutanud romaani, mis on seatud universumisse, kus P = NP , juhul kui neid on rohkem kui üks, mis oli esimene?

enter image description here

Selles universumis said kõik probleemid, mida oli võimalik kontrollida polünoomiajas (NP) (antud lahendus), lahendada ka polünoomiajas (P).

mõjuval põhjusel ma kujutaksin ette. Näen dialoogi praegu.
Greg Egan kirjutas tumedad täisarvud ja Luminous, mis käsitlevad arvutatavust ja keerukust puhta algebra seadetes. Kui see õnnestub, siis võib ka romaan P = NP kohta olla
Mitte romaan, vaid Russell Impagliazzo (tipp-keerukusteooria uurija) kirjutas lühikese töö, milles kirjeldati viit maailma, kus sellised asjad juhtuvad (universumis Algorithmica on P = NP, krüptomania on taganud avaliku võtme krüptograafia jne). Mõtlesin lihtsalt, et mainin ära juhuks, kui soovite uudistada teoreetilisemat vaatenurka selle kohta, milline võiks olla P = NP maailm. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr G +1, kuid ma pole kindel, milliseid versioone Egani lühijuttudest olete lugenud: P Tulemused olid nende tõeväärtuste ümberlükkamine, kahjustades „teist, paralleelset universumit”. Füüsikat ennast mõjutas matemaatikareeglite muutmine, nii et "teiste" vastu võitlemisel valitses kõikjal kaos. (Ja jah, mul on puhas matemaatika doktorikraad)
... ja kuidas sa tead, et P = NP pole meie universumis tõsi? Andke mulle teada ja ma jagan teiega 1 miljon dollarit.
@DavidRoberts oleksin pidanud selle küsimuse sõnastama romaanina, mis asetseb universumis, kus me teame, et P = NP :) Re: Egan, tõlgendasin lugu intensiivse määratluse keerdkäiguna. Meie teooria põhineb intensiivsel määratlusel, ei tähenda, et universum oleks sellega nõus, ja kuna me pole proovinud oma definitsioonide ekstensiivset versiooni kontrollida, võib füüsiline universum sellega nõustuda.
Võib-olla neid kõiki ... Kuna see on praegusel hetkel lahendamata probleem. :-)
[MathFiction Homepage] (http://kasmana.people.cofc.edu/MATHFICT/) oleks hea lähtepunkt millegi sellise jaoks.
Kas oskate * tõesti * lihtsate sõnadega selgitada, mida tähendab P = NP ja kuidas saaksime teada, kas meie loetud raamat oleks selles universumis?
@Wikis: P = NP universumis _leides_, oleks suure ja täpselt määratletud probleemide hierarhia õige lahendus ainult sama keeruline kui _tundes, et sellise probleemi pakutud lahendus on õige. Näiteks meie universumis tundub kunstiteose suurepärase äratundmine palju lihtsam kui suurepärase teose loomine. Universumis, kus P = NP, oleks vajaliku pingutuse summa sama või lahendatava probleemi suuruse järgi vaadates vaid tagasihoidlikult suurem. Peaaegu kõigi krüptimisvormide lihtne krakkimine on veel üks P = NP universumi märk.
@DrG: Greg Egan võiks ilmselt kirjutada romaani, kus P ja NP on peategelased. See mees teeb Kim Stanley Robinsoni sarnaseks George Lucasega.
Kümme vastused:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

Star Trek, Various, 1966 (varaseim sündmus)

P = NP Star Treki universumis, kuid sealsed inimesed pole sellest teadlikud. Tõendid ://

  1. Krüpteerimist on, kuid see on alati purunev. P = NP võimaldab teil murda kõike peale ühekordsete klotside, kuid föderatsioon jätkab visalt NP-põhiste šifreid.

  2. Universaalse tõlgi tõhusus. P = NP muudaks uute keelte õppimise imelihtsaks, vähemalt arvuti jaoks. Õppimissüsteemide rakendamine oleks nii lihtne ja arusaadav, et töökohale ei jääks keeleteadlast.

  3. Biofiltri tõhusus. Transporter filtreerib rutiinselt tundmatuid organisme, viirusi ja muid ohte, kui meeskonnaliikmeid laeval pardal on. Kuid "biofilter" on eksitav termin, kuna see toob meelde mingisuguse sõela, mis haarab kinni kõik halvad asjad ja läbib ainult head. Tegelikkuses oleks sellise "filtri" käitamine transpordiandmete üle kõigi indutseeritud alamgraafi isomorfismiprobleemide ema, kuna peate identifitseerima kõik viiruse suurused struktuurid organismis, mis on selliseid struktuure täis. P = NP võlub sisendiga seotud eksponendi ära, mis muudab sellised probleemid lahendamatuks ka väikeste graafikute puhul.

  4. Eneseteadlik masintarkus luuakse hõlpsalt. Wesley Crusher lõi ühe kogemata. Nii tegi ka Richard Daystrom. Enterprise D arvuti küpsetas Moriarty oma varutsüklites, dr Farallon lõi Exocompsi jne. Tundub, et peate vaid looma midagi, mis on samaväärne teoreemi tõestava süsteemiga, ja laskma sellel piisavalt kaua töötada, et komistada tõestusest, et P või mõni muu jälgitav klass on võrdne NP-ga ja süsteem on võistlustelt väljas.

Või võib-olla kukuvad Star Treki elanikud polünoomhierarhiat tehnoloogiliste vahenditega kokku. Näib, et föderatsioonil, Borgil jms on ajamasinatele, ussiaukudele, eksootilistele ainetele ja üliluminaalsele signaalimisele hõlpsasti juurdepääs, seega võiksid nad arvutamiseks kasutada suletud ajataolisi kõveraid. See Scott Aaronsoni sõnul võimaldaks neil PSPACE-ga seotud probleeme tõhusalt lahendada.
+1 selle eest, et kasutasite kogu maailma tõendeid mõne asja näitamiseks. Suurepärane.
Ma arvan, et nad tegelevad vaid teie esitatud kolme punktiga toore arvutusvõimsuse abil. DTM suudab lahendada täpselt samu probleeme nagu NTM, kuid see võtab kauem aega. Niisiis, kui nende insenerioskused on piisavalt hullud, võivad nad köhida väga kiiresti (paralleelselt) arvuteid (samuti leidsid nad teekonnal tõenäoliselt mõne toreda heuristika mõnede NP-raskete probleemide jaoks). Nii et ma pole kindel, kuidas teie argumendid kehtivad.
@Blue Võib-olla oleksin pidanud kirjutama, et P = NP võimaldab teil murda kõik _kasulikud_, kuid ühekordsed padjad. Kui te ei saa dekrüpteerimist polünoomiajal kontrollida, mis tähendab seda, et krüptosüsteemi omamine väljaspool NP-d ei ole, pole ka võtmega_ dekrüpteerimine arvutuslikult teostatav. See pole minu jaoks kasulik krüptosüsteem.
@bitmask: Star Trek juhib arvuti südamikku muudetud lõimeväljas, kus aeg kulgeb erineva kiirusega.
@MichaelEdenfield: Kui * on * probleemide lahendamise tehnikaid, mis on rangelt võimsamad kui väga kiire DTM, ning praktiliste rakenduste jaoks on P ja NP kaotanud oma tähtsuse, on see iseenesest väga tugev tõend P = NP kohta universumis. P! = NP universumis on selliste tehnikate avastamine väga ebatõenäoline.
@Tynam P ja NP on määratletud rangelt selle järgi, mida on võimalik teha deterministlike ja mittemääravate Turnigi masinatega; neist pole lihtsalt mõtet rääkida väljaspool seda konteksti. Juba on tõendeid selle kohta, et kvantarvutid * võivad * pakkuda viisi näiteks mitte-deterministlike arvutuste tegemiseks ...
@MichaelEdenfield: Hea punkt; Ma ei olnud kvantarvuti / NDTM-nurga läbi mõelnud. See tähendab, et praktiline erinevus P = NP universumi ja oluliselt võimsama ND-arvutusliku universumi vahel näib tõenäoliselt väike. (Kuid siis pole ma veendunud, et inimese aju on sisuliselt võimsam kui DTM; paralleelsus ei ole sama mis algoritmiline keerukus.)
Kas saaksite sellele kuupäeva panna?
@AncientSwordRage kuupäev milleni?
@Kyle - kuupäev, millal teie arvates täherännakute sarju esimest korda kujutati kui P = NP.
@AncientSwordRage Minu näidete hulgast valides arvan, et see peaks olema esimene episood, kus kasutatakse universaalse tõlgi kasutamist esimese kontakti olukorras.TOS-is oleks see esimese hooaja 10. jagu, "Corbomite'i manööver", kui * Enterprise * kohtus Baaloki ja Esimese Föderatsiooni lõbusaga.
@kyle, mis teeb selle 1966. aastaks, mis on kandidaat.Kas oleksite selle vastu, et ma seda teie vastusesse muudaksin?
@AncientSwordRage nope, mine edasi.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

Antikehad, Charles Stross, 2000

Lühijutt, mis sõltub asjaolust, et P = NP lahendamine on arvuti intelligentsuse arendamise vajalik eeltingimus. See on saadaval tema raamatus röstsai . Stross on selle raamatu täisteksti võrku pannud. ( See link viib teid otse loo juurde.)

Ja Strossi saidi andmetel oli lugu järgmine:

Avaldatud Interzone'is # 157; uuesti avaldatud ajakirjas "Aasta parim ulme nr 18" (toim. Gardner Dozois). Mainitud Locuse 2000. aasta „Soovitatavas lugemisloendis”. 2001. aasta Theodore Sturgeoni auhinna nimekirja pääsenud (kaotatud Ian MacDonaldi „Tendoleo loole”).

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

Teine Strossi raamat, mis sellega tegeleb, on The Atrocity Archives, kus Alan Turing lahendas P = NP, kuid leidsid siis, et see võimaldas juurdepääsu Cthonic Realmsile, nii et nüüd terve haru on olemas selleks, et vältida selle avastuse avalikkusele teatavaks saamist.

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

Vernor Vinges'i sarjas "Mõttevööndid" ("Blabber", Tulekahju sügavale , Sügavus taevas ja peagi ilmuvad The Taeva lapsed ), arvutamine on galaktika mõnes osas lihtsam, võimaldades selliseid asju nagu tehisintellekt ja FTL-reisimine.

On spekuleeritud (kuid raamatutes pole otseseid tõendeid), et P = NP nendes tsoonides.

Kas on kaudseid tõendeid? Mäletan, et väljaspool aeglast tsooni on arvutus erinev (Kiriku väitekiri kehtib ainult aeglases tsoonis) ja midagi sellist nagu P = NP ei pea seal kehtima ega isegi mõtet olema.
Väljaandes * Tulekahju sügaval * leiavad Skode'i ratturid, et Phami usk avaliku võtme krüptimisse on humoorikas. Selle põhjal võime järeldada, et `P == NP` väljaspool seda.
Mitte tingimata - kvantarvutid saaksid teoreetiliselt lahendada NP-täielikke probleeme polünoomiajas, isegi ilma P = NP-ta.
Ei nad ei saa. Toimingud, millele kõige levinumad avaliku võtme krüpteerimisalgoritmid tuginevad, on keerukad - faktooring, diskreetne logi - ei ole (arvatavasti) NP-täielik. Need on probleemid, mida kvantarvutid suudavad teoreetiliselt polünoomiajas murda. Nagu öeldud, on olemas avaliku võtmega krüptimisalgoritme, mis * põhinevad NP-täielikul probleemil, kuid neid pole veel laialdaselt kasutatud (veel ...)
@BlueRaja Me ei tea praegu, kuidas kvantarvutit NP täielike probleemide tõhusaks lahendamiseks kasutada, kuid te väidate, et `P
@Code: Jah, vabandust, et ma ei rääkinud ettevaatlikult. Ma mõtlesin, et see pole * teada * (või arvatakse), et see on teoreetiliselt võimalik.
Ma kavatsesin öelda mõttevööndid. Ma pole kindel, kas see on sõna otseses mõttes tõsi, et P = NP, kuna on võimalik, et _tsoonis igas konkreetses asukohas_, kehtib meie sisetunne, et saate luua NP-probleemi, mida te ei saa lihtsalt lahendada Kuid ma arvan, et see on piisavalt sarnane, et seda mainimist vääriks, kuna saate liikuda (või saata sõnumi) kõrgemasse tsooni, kus teie probleem on hõlpsasti lahendatav.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

Eliezer S. Yudkowsky fännilises Harry Potteris ja ratsionaalsuse meetodites saab Harry endale ajamasina ja proovib kahe suure algarvu korrutust arvutada, kasutades see masin, mõnevõrra imeliku tulemusega. Nii et pole täielikult antud, et NP = P , vaid tundub tõenäoline.

Sellel pole mõtet. Probleem kuulub P-i, kui on olemas teatud probleemi lahendav Turingi masin (NP määratlus on sarnane). Pole tähtis, kas selle probleemi lahendamiseks on muid mõeldavaid vahendeid. Ajasilmuste häkkimisega jõudis Harry P = NP küsimusest kaugemale.
Jah, kui tema test õnnestus, oleks see tähendanud, et on olemas „tugevam” arvutiseade kui Turingi masin, ja seetõttu lükkas ta kiriku väite ümber. Nii et kui lahkute NP-st Turingi masinate abil määratletud kujul, ei tõenda see 'NP = P'.
IIRC, on tõestatud, et P = PSPACE (mis on tugevam kui P = NP) Turingi masinale, mis on varustatud andmete õigeaegse tagurpidi saatmisega, isegi kui see allub Novikovi enesekindlusele.Ikka on võimalik, et P = PSPACE tavaliste Turingi masinate jaoks, kuid peavoolu keerukusteoreetikud peavad seda veelgi vähem usutavaks kui P = NP.
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

Möirgav trompet , autorid Spague de Camp ja Fletcher Pratt, avaldatud 1940. aasta mais teadmatuses. Siinkohal arvavad psühholoogid, et skisofreenikud pääsevad vaimselt juurde asendusuniversumitesse ja õigeid võrrandeid rakendades võiks rännata sellesse asendusuniversumisse ja tuua inimeste meeled tagasi meie universumisse. See oli intellektuaalne õppus, mille peategelane Harold Shea otsustas katsetada. Ta viitab naljatades reisimisele syllogismobile'i kaudu, kuid see hõlmab universumi sihtkoha loogika uurimist ja ülesehitamist ning selle valjusti ettelugemist. See algab üldjuhul "kui P on võrdne mitte P-ga ..." Ja läheb sealt edasi. Kogu Enchanteri seerias laseb neil universum hüpata läbi mütoloogia ning muinasjuttude ja klassikaliste teoste.

Ma kahtlustan, et pole kunagi sellele reaalselt mõelnud, et P universum kui selline, milles maagia toimib.

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

Nemesis, Isaac Asimov, 1989

See räägib võimatustest ja universumi tagajärgedest, kus füüsikaseadused ei kehti

Palun esitage järgmine kord oma vastusega kuupäev ja selgitage, miks see on * selgesõnaliselt seotud P = NP-ga.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

Praktikaefekt , David Brin, 1984

See tundub tõenäoline kandidaat. Kujutatud universumis hakkab meie universumi robotproov optimeerima nii füüsiliselt kui ka vaimselt, samal ajal kui inimese intelligentsus jääb muutumatuks. Ka füüsilised esemed kipuvad ennast optimeerima: puidust kelk arendab libestit, mis hõlpsasti teel libiseda. Seda praktikaefekti saab suurendada spetsiaalse transiseisundiga, kus lahendus ilmub kohe iseenesest, mistõttu elutud objektid teostavad mittepolünoomse aja jooksul laiaulatuslikku evolutsiooni (võimalikult lühikese aja jooksul võimalike võimalike lahenduste hulga otsimine) . See universum ületab tegelikult P = NP.

Palun [redigeeri], miks see teie arvates nii on.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

Margaret Weisi ja Tracy Hickmani loos Starshield Sentinels leidus arvuteid / tehisintellekte, mis suutsid igale küsimusele vastata koheselt saates küsimuse ajas tagasi iseendale , andes selle lahendamiseks aega. Ainus luksumine oli see, et arvuti pidi selle lahendamiseks olema piisavalt kaua "ärkvel" (midagi sellist nagu "Sügav mõte" The Hitchhiker's Guide to the Galaxy vajab 10 miljonit aastat küsimuse lahendamiseks elus, universumis ja kõiges).

Kuigi ma ei tea, kas see puudutab täpselt kõike P = NP, lahendab see küsimuses muutuja / lahenduse klausli.

Muidugi lähevad kõik arvutid pähe ja üritavad loos kõiki tappa. Kas me ei saa nüüd mõrvaroboteid leiutada?

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

Kui ma ei eksi, veedab Bob Shaw teoses „ The Ragged Astronauts” tegelastest natuke aega, selgitades, kuidas pi on 3 teisele. Kui pi on 3, võin ainult ette kujutada, milline on ülejäänud füüsika. (Ma mäletan seda stseeni üldse ainult seetõttu, et kogu stseen oli veidi paigast ära, mis oli raamatu jaoks üsna ebatavaline - muidu oli see puhas lugu).

Kuidas on see seotud p = np-ga?


See küsimus ja vastus tõlgiti automaatselt inglise keelest.Algne sisu on saadaval stackexchange-is, mida täname cc by-sa 2.0-litsentsi eest, mille all seda levitatakse.
Loading...