Does Douglas Adams bruge 'Uendelig Utilstrækkelighed' til P = NP?

7

Efter at have lige vågnet det gamle P = NP -post begyndte jeg at tænke: Er Douglas Adams beskrivelse af opdagelsen af det uendelige improbability-drev via brug af den endelige improbabilitetsenhed en beskrivelse af, hvor P = NP bruges til at løse et problem? Er dette hans forklaring på problemet?

Mit punkt, forklaret: Det er min forståelse, at "forskerne" opdagede det endelige usandsynlighedsdrev, ved hjælp af en algoritme eller forståelse, som lader dem sætte i de rigtige parametre, dreje et matematisk håndtag og ud af den endelige improbablity-drev, vidste de gættet arbejde. De forsøgte derefter at finde det uendelige usandsynlighedsdrev på samme måde, anvende en algoritme og dreje håndtaget.

Men dette tog for lang tid (det var ikke polynomisk tid, måske var det N ^ p, med p at være sandsynligheden), så forskerne gav op. Opdageren af IID brugte imidlertid Finite Improbability-drevet til at gætte løsningen på uanset algoritme eller ligning, og parametrene involverede, dvs. han løste det som et P-problem som et NP-problem.

Jeg kan ikke finde noget på nettet, der diskuterer dette, men jeg har muligvis savnet noget.

Er dette (eller noget lignende), hvad Douglas Adams betød med denne beskrivelse? Hvis ikke, hvad mener han?

    
sæt AncientSwordRage 26.09.2012 / 12:02
kilden

4 svar

7

Sort af.

En måde at definere NP på er, at spørgsmålet kan afgøres i polynomisk tid givet adgang til ikke-determinisme . Som det viser sig, kan ikke-determinisme betragtes som ækvivalent med at have en computer, der lykkes, hvis den har en nul sandsynlighed for succes. I det væsentlige svarer ikke-determinisme til den endelige sandsynlighedsenhed.

Så givet en enhed som en endelig usandsynlighed enhed, enhver usandsynlig begivenhed kan gøres sandsynlig. Vi kan bruge det til at opbygge en computer, der har adgang til ikke-determinisme. Skelnen mellem P og NP er så mødt, fordi P og NP kører med samme hastighed på en nondeterministisk computer. Teoretisk set er P og NP stadig forskellige, men sondringen er ikke længere nyttig.

    
svar givet 26.09.2012 / 21:58
kilden
7

Det er værd at bemærke, at N i NP ikke kun kan anvendes på polynomeproblemer: Hvis X er et bestemt sæt af problemer , der kan afgøres i en tid, der er afgrænset af en given karakterisering er polynom for P eller eksponentiel for EXP ) ved en deterministisk Turing Machine (DTM), så vil NX være det sæt af problemer, der kan afgøres af en ikke-deterministisk Turing Machine (NTM).

Så spørgsmålet er, hvordan FID virkelig virker. Er du nødt til at løse et problem, der kan afgøres af en DTM i polynomisk tid hver gang du vil hoppe? Hvis du har bygget en maskine, der brugte FID'en til at fjerne den nødvendige ikke-determinisme fra en TM-løb, ville du i det væsentlige have bygget en NTM. Dette giver faktisk mening, for selv om problemrummet er (eller måske måske er) uendeligt, er en bestemt forekomst af problemet altid begrænset. Så sandsynligheden for altid at "gætte" korrekt er endelig. I den forstand vil FID være det teknologiske svar til beregningsmodellen for en NTM. Så generelt, i et univers med en FID, er der ingen praktisk forskel mellem X og den tilsvarende NX klasse af problemer, men det ville stadig være ukendt, om de rent faktisk er lige (som de er defineret over TM'er, ikke ID'er).

Det er dog ikke fornuftigt at argumentere for den samlede runtime af en algoritme, der knytter en uendelig indgang, som i alle sammen, men nogle trivielle tilfælde, der også ville være uendelige.

Hvis IID er bare en slags matematisk problem, der engang løst bare hænder, har du et vis indblik i at bygge en maskine, der implementerer en slags fremdrift, så spørgsmålet er, hvor svært er dette problem? Vi har ingen tegn på, at det ville falde i klassen NP -komplette problemer. Der er et ton på PSPACE (= NPSPACE ) problemer, og faktisk endda ca. NEXPTIME . Hvis det var PSPACE ville din magiske avanceret teknologisk FID ikke være til nytte for dig, du ville vente lige så længe.

Så forholdet mellem enhver X og NX ville være som "fast usandsynlighed drev" og "endelig usandsynlighed drev". Det ser ud til, at uendelig usandsynlighedsdrev vil snarere svare til en maskine, der bestemmer hvert eneste problem i konstant tid, uanset dens kompleksitet på en DTM eller NTM, fordi en uendelig usandsynlig Begivenhed er stort set en, der aldrig sker. Der er ingen sådanne begivenheder tænkelige: Selv to kernekrigshoveder spontant omdannes til en skål petunier, og en meget overrasket ser spermhval er ikke en umulig begivenhed. Det er bare så usandsynligt, at ingen plager at lægge et advarselsstik på sådanne warheads.

For at endelig besvare dit spørgsmål så; Nej, jeg tror ikke Adams ville have gjort sådan en pop-science blunder. Hans wibbly-wobbly dele (i mangel på en bedre periode) er altid forsætlige og arbejder mere ironisk. IID minder os lidt om det ikke-determinismiske problem, da det gør noget skræmmende hårdt på en spektakulært effektiv måde, ligesom et NTM ville. Men denne lighed er ret overfladisk, som jeg forsøgte at påpege i de foregående afsnit.

    
svar givet 27.09.2012 / 02:27
3

Jeg tror, at du kunne bruge et uendeligt usandsynlighedsdrev som en del af en NP-løsning, der ville gøre P = NP.

Sig du tune din IID, så når du tilfældigt vælger en kandidatløsning, giver den dig den egentlige løsning. Pr. Definition er det forholdsvis nemt at verificere løsningens rigtighed for NP-problemer.

Udført.

Den hårde del får det uendelige usandsynlighedsdrev.

    
svar givet 26.09.2012 / 18:22
2

Jeg kan ikke se, hvordan det kunne være tilfældet. Meget kort er P og NP to klasser af beregningsmæssige problemer. P-problemerne kan løses inden for en rimelig periode med velkendte algoritmer. NP-problemerne menes (men endnu ikke bevist) at være sådan, at den eneste måde at løse dem på er at prøve enhver mulig løsning i det væsentlige tilfældigt, indtil du får det rigtige svar. Men alle NP-problemer ligner på en måde, at hvis du opdagede en algoritme, der tillod dig at løse en NP hurtigere, ville algoritmen gælde for alle andre NP-problemer. Hvis du nogensinde har tinkered med matematikken, der viser, hvor mange mulige løsninger der findes i løsningsrummet, kan du se hvorfor det var en stor ting. Numre i nogle tilfælde, der er så store, de har ingen navne, kun noteringer.

Der er reelle verdensimplikationer, hvis P tilfældigvis er lige NP (og få, som vi ikke allerede lever, hvis det ikke gør det). For eksempel er et sådant problem "Giv en leveringsrute til disse 100 steder, som er den mest effektive rute at tage". Hvis du kunne løse det i løbet af et rimeligt tidsrum, ville dit leveringsselskab (sandsynligvis) bruge 5% mindre brændstof om året. Til gengæld en 5% reduktion fra nogle store flyselskaber, og vi vil nok se $ 1,50 / gallon benzin igen i USA. Og der er mange sådanne problemer. Computer grafik, meteorologi simuleringer, mange af dem. P = NP har mange real-world science-fictiony implikationer (for det meste beskæftiger sig med effektivitet).

Men øjeblikkelig rejse til fjerne steder er ikke en af dem.

    
svar givet 26.09.2012 / 14:41