Efter att ha just väckt det gamla P = NP -posten började jag tänka: Är Douglas Adams beskrivning av upptäckten av den oändliga improbability-enheten via användningen av Finite Improbability-enheten en beskrivning av var P = NP används för att lösa ett problem? Är detta hans förklaring av problemet?
Min punkt, förklarad: Det är min förståelse att "forskarna" upptäckte den ändlösa sannolikhetsdriften, genom någon algoritm eller förståelse som låter dem sätta i rätt parametrar, vrida ett matematiskt handtag och klara av den slutgiltiga improbablity-enheten, visste de att gissningen fungerade. De försökte sedan hitta den oändliga sannolikhetsdriften på samma sätt, tillämpa en algoritm och vrida handtaget.
Men detta tog för lång tid (det var inte polynomaltid, det var kanske N ^ p, med p som sannolikheten) så forskarna gav upp. Upptäckten av IID använde dock Finite Improbability-enheten för att gissa lösningen på vilken algoritm eller ekvation som helst, och parametrarna inblandade, dvs han löst det som ett P-problem som ett NP-problem.
Jag kan inte hitta något på webben som diskuterar detta, men jag kan ha saknat något.
Är detta (eller något liknande) vad Douglas Adams menade med den här beskrivningen? Om inte vad menade han?
Sort av.
Ett sätt att definiera NP är att frågan kan avgöras i polynomisk tid som ges åtkomst till icke-determinism . Som det visar sig kan icke-determinism anses som likvärdig med att ha en dator som lyckas om den har en noll sannolikhet för framgång. I huvudsak är icke-determinism ekvivalent med den slutgiltiga sannolikhetsanordningen.
Så givet en enhet som en begränsad osannolikhet, kan en osannolik händelse göras sannolikt. Vi kan använda det för att bygga en dator som har tillgång till icke-determinism. Skillnaden mellan P och NP är då moot, eftersom P och NP kör i samma hastighet på en icke-bestämd dator. Teoretiskt är P och NP fortfarande distinkta, men skillnaden är inte längre användbar.
Det är värt att notera att N i NP inte bara kan tillämpas på polynomproblem: Om X är en särskild uppsättning problem som kan avgöras under en tid som begränsas av en given karakterisering är polynom för P eller exponentiell för EXP ) av en deterministisk Turing Machine (DTM), så kommer NX att vara det uppsättning problem som kan bestämmas av en icke-deterministisk Turing Machine (NTM).
Så frågan är hur FID verkligen fungerar. Måste du lösa ett problem som kan avgöras av en DTM i polynomaltid varje gång du vill hoppa? Om du byggde en maskin som använde FID för att avlägsna den nödvändiga icke-determinismen från en TM-körning, skulle du väsentligen ha byggt en NTM. Det här är verkligen meningsfullt, för även om problemutrymmet är (eller snarare kan vara) oändligt, är en viss förekomst av problemet alltid ändlig. Så sannolikheten att alltid "gissa" korrekt är ändamålsenlig. I detta avseende skulle FID vara tekniskt ekvivalent med beräkningsmodellen för en NTM. Så i allmänhet, i ett univers med en FID, finns det ingen praktisk skillnad mellan någon X och dess motsvarande NX klass av problem, men det skulle fortfarande vara okänt om de faktiskt är lika (som de är definieras över TM, inte ID-er).
Men det är inte meningsfullt att argumentera för den totala körtiden för en algoritm som crunches en oändlig inmatning, som i alla fall, men några triviala fall som också skulle vara oändliga.
Om IID är bara ett slags matematiskt problem, som en gång löst bara händer, får du viss inblick i att bygga en maskin som implementerar någon form av framdrivning, då är frågan hur svårt det här problemet är? Vi har ingen aning om att det skulle falla i klassen NP -komplett problem. Det finns massor av PSPACE (= NPSPACE ) problem, och faktiskt även cirka NEXPTIME . Om det var PSPACE skulle din magiska avancerad teknisk FID inte vara till nytta för dig, du väntar lika länge.
Så förhållandet mellan X och NX skulle vara som "fast sannolikhetskörning" och "ändlig osannolikhetskörning". Det verkar som om oändlig osannolikhetsdriven snarare skulle motsvara en maskin som bestämmer varje enskilt problem i konstant -tid, oavsett komplexitet på en DTM eller NTM eftersom en oändligt osannolik händelsen är i grunden en som aldrig händer. Det finns inga sådana händelser tänkbara: Till och med två kärnvapenhoppar spontant förvandlas till en skål med petunier och en mycket förvånad ser spermhval är inte en omöjlig händelse. Det är bara så osannolikt att ingen plågar att lägga en varningsstämpel på sådana warheads.
För att slutligen svara på din fråga då; Nej, jag tror inte att Adams skulle ha gjort en sådan pop-science blunder. Hans wibbly-wobbly delar (i avsaknad av en bättre term) är alltid avsiktliga och arbetar mer på ett ironiskt sätt. IID påminner oss lite om det icke-determinismiska problemet eftersom det gör någonting skrämmande hårt på ett spektakulärt effektivt sätt, precis som en NTM skulle. Men denna likhet är ganska ytlig, som jag försökte påpeka i tidigare stycken.
Jag tror att du kan använda en oändlig osannolikhetsdrivenhet som en del av en NP-lösare som skulle göra P = NP.
Säg att du stämmer med din IID så att när du slumpmässigt väljer en kandidatlösning, ger den dig den verkliga lösningen. Enligt definitionen är det relativt enkelt att kontrollera att lösningen är korrekt för NP-problem.
Klar.
Den svåra delen får den oändliga osannolikheten.
Jag förstår inte hur det kan vara fallet. Mycket kortfattat, P och NP är två klasser av beräkningsproblem. P-problemen kan lösas inom en rimlig tidsperiod med välkända algoritmer. NP-problemen tros (men ännu inte bevisat) vara så att det enda sättet att lösa dem är att försöka alla möjliga lösningar i huvudsak slumpmässigt tills du får rätt svar. Alla NP-problem liknar emellertid på ett sätt som om du upptäckte en algoritm som gjorde det möjligt för dig att lösa en NP snabbare, skulle den algoritmen gälla alla andra NP-problem. Om du någonsin har tinkered med matematiken som visar hur många möjliga lösningar som finns i lösningsutrymmet, kan du se varför det var en stor sak. Numrer i vissa fall som är så stora de har inga namn, bara noteringar.
Det finns verkliga världsimplikationer om P råkar vara lika med NP (och få som vi inte redan lever om det inte gör det). Ett sådant problem är till exempel "Givet en leveransväg till dessa 100 platser, vilket är den mest effektiva vägen att ta". Om du skulle kunna lösa det inom en rimlig tid skulle ditt leveransföretag (förmodligen) använda 5% mindre bränsle per år. I sin tur, en minskning med 5% från några stora operatörsfartyg, och vi skulle förmodligen se $ 1,50 / gallon bensin igen i USA. Och det finns många sådana problem. Datorgrafik, meteorologisimuleringar, många av dem. P = NP har många verkliga science-fictiony implikationer (mestadels handlar om effektivitet).
Men omedelbar resa till avlägsna platser är inte en av dem.
Läs andra frågor om taggar hard-sci-fi science the-hitchhikers-guide-to-the-galaxy Kärlek och kompatibilitet Skor Gear 12 Stjärntecken Grunderna