verwijst Douglas Adams naar 'Infinite Improbability' naar P = NP?

7

Nu ik het oude P = NP -bericht opnieuw heb gewekt, begon ik te denken: is de beschrijving van Douglas Adams van de ontdekking van de Oneindige Snelheid door middel van het gebruik van het Eindige Apparaat van de Onbetrouwbaarheid een beschrijving van waar P = NP wordt gebruikt om een probleem op te lossen? Is dit zijn uitleg van het probleem?

Mijn punt, opnieuw uitgelegd: het is mijn inzicht dat de 'wetenschappers' de eindige onwaarschijnlijkheid hebben ontdekt, door een algoritme of enig begrip dat hen de juiste parameters laat zetten, een wiskundig handvat aanzet en haal de eindige improbabiliteiten weg, ze wisten dat het giswerk binnenkwam. Ze probeerden toen de oneindige onberekenbaarheidsdrive op dezelfde manier te vinden, pasten een algoritme toe en zwengelden aan het handvat.

Maar dit duurde te lang (het was geen polynomiale tijd, misschien was het N ^ p, waarbij p de waarschijnlijkheid was) dus de wetenschappers gaven het op. De ontdekker van de IID gebruikte echter de Finite Improbability-schijf om de oplossing te raden voor elk algoritme of elke vergelijking, en de betrokken parameters, d.w.z. hij loste het op als een P-probleem als een NP-probleem.

Ik kan op internet niets vinden dat dit bespreekt, maar ik heb misschien iets gemist.

Is dit (of iets soortgelijks) wat Douglas Adams met deze beschrijving bedoelde? Zo niet, wat bedoelde hij dan?

    
reeks AncientSwordRage 26.09.2012 / 12:02

4 antwoord

7

Sortering van.

Een manier om NP te definiëren is dat de vraag kan worden besloten in polynomiale tijd, gegeven toegang tot niet-determinisme . Zoals blijkt, kan non-determinisme worden beschouwd als gelijkwaardig aan het hebben van een computer die slaagt als deze een kans van ongelijkheid van nul heeft. In wezen is niet-determinisme equivalent aan het eindige waarschijnlijkheidsapparaat.

Dus als een apparaat als een eindig onwaarschijnlijkheidsapparaat wordt gegeven, kan elke onwaarschijnlijke gebeurtenis waarschijnlijk worden gemaakt. We kunnen dat gebruiken om een computer te bouwen die toegang heeft tot niet-determinisme. Het onderscheid tussen P en NP is dan onbewezen, omdat P en NP op dezelfde snelheid draaien op een niet-deterministische computer. Theoretisch zijn P en NP nog steeds verschillend, maar het onderscheid is niet langer bruikbaar.

    
antwoord gegeven 26.09.2012 / 21:58
7

Het is de moeite waard op te merken dat de N in NP niet alleen kan worden toegepast op polynomiale problemen: als X een bepaalde reeks problemen is, die kan worden beslist in een tijd die wordt begrensd door een gegeven karakterisering (die is, polynoom voor P of exponentieel voor EXP ) door een deterministische Turingmachine (DTM), dan zal NX de reeks problemen zijn die kan worden bepaald door een niet-deterministisch Turingmachine (NTM).

Dus de vraag is hoe de FID echt werkt. Moet u een probleem oplossen dat door een DTM in polynomiale tijd kan worden beslist telkens als u wilt springen? Als u een machine hebt gebouwd die de FID heeft gebruikt om het vereiste niet-determinisme uit de run van een TM te verwijderen, zou u in feite een NTM hebben gebouwd. Dit is eigenlijk logisch, want hoewel de probleemruimte oneindig is (of beter gezegd) kan zijn, is een bepaald geval van het probleem altijd eindig. Dus de kans om altijd correct te "raden" is eindig. In die zin zou de FID het technologische equivalent zijn van het computermodel van een NTM. Over het algemeen is er dus in een universum met een FID geen praktisch verschil tussen een willekeurige X en de bijbehorende NX -klasse van problemen, maar het zou nog steeds onbekend zijn of ze in feite gelijk zijn (zoals ze zijn gedefinieerd via TM's, geen ID's).

Het heeft echter geen zin om te argumenteren over de totale looptijd van een algoritme dat een oneindige invoer verwerkt, zoals in alle, behalve enkele triviale gevallen, die ook oneindig zijn.

Als IID slechts een soort van wiskundig probleem is, dat eenmaal opgelost, geeft het je enige inzicht om een machine te bouwen die een soort van voortstuwing implementeert, dan is de vraag hoe moeilijk dit probleem is? We hebben geen enkele aanwijzing dat het zou vallen in de klasse van NP -complete problemen. Er zijn een ton van PSPACE (= NPSPACE ) problemen, en eigenlijk zelfs zo'n NEXPTIME . Als het PSPACE je magische geavanceerde technologische FID niet zou gebruiken, zou je net zo lang wachten.

De relatie tussen X en NX zou dus lijken op "fixed improbability drive" en "finite improbability drive". Het lijkt erop dat de oneindige onwaarschijnlijkheidsdrempel eerder overeenkomt met een machine die elk afzonderlijk probleem in constante -tijd bepaalt, ongeacht de complexiteit ervan op een DTM of NTM omdat een oneindig onwaarschijnlijk is evenement is in feite een evenement dat nooit plaatsvindt. Dergelijke gebeurtenissen zijn niet denkbaar: zelfs twee kernkoppen die spontaan veranderen in een schaal met petunia's en een zeer verbaasd uitziende potvis is geen onmogelijke gebeurtenis. Het is zo onwaarschijnlijk dat niemand een waarschuwingssticker op dergelijke kernkoppen plaatst.

Om eindelijk je vraag te beantwoorden; Nee, ik denk niet dat Adams zo'n pop-science blunder zou hebben gedaan. Zijn wibbly-wobbly delen (bij gebrek aan een betere term) zijn altijd opzettelijk en werken meer op een ironische manier. De IID herinnert ons enigszins aan het probleem van niet-determinisme, omdat het iets verbijsterend hard doet op een spectaculair efficiënte manier, net zoals een NTM dat zou doen. Maar deze gelijkenis is nogal oppervlakkig, zoals ik in voorgaande paragrafen heb geprobeerd te benadrukken.

    
antwoord gegeven 27.09.2012 / 02:27
3

Ik geloof dat je een combinatie van oneindige onwaarschijnlijkheid zou kunnen gebruiken als onderdeel van een NP-oplosser die P = NP zou maken.

Stel dat u uw IID afstemt, zodat u bij het willekeurig selecteren van een kandidaat-oplossing de daadwerkelijke oplossing krijgt. Per definitie is het voor NP-problemen relatief eenvoudig om de juistheid van de oplossing te verifiëren.

Gereed.

Het moeilijkste is om de oneindige onwaarschijnlijkheid te krijgen.

    
antwoord gegeven 26.09.2012 / 18:22
2

Ik zie niet hoe dat het geval zou kunnen zijn. Heel kort, P en NP zijn twee klassen van rekenproblemen. De P-problemen kunnen binnen een redelijke termijn worden opgelost met bekende algoritmen. Er wordt aangenomen dat de NP-problemen (maar nog niet bewezen) zodanig zijn dat de enige manier om ze op te lossen is om elke mogelijke oplossing in wezen willekeurig te proberen totdat je het juiste antwoord krijgt. Alle NP-problemen zijn echter vergelijkbaar op dezelfde manier dat als u een algoritme zou hebben ontdekt waarmee u sneller een NP zou kunnen oplossen, dit algoritme van toepassing zou zijn op alle andere NP-problemen. Als je ooit hebt gesleuteld met de wiskunde die laat zien hoeveel mogelijke oplossingen er in de oplossingsruimte bestaan, zou je kunnen zien waarom dit een groot probleem was. Getallen in sommige gevallen die zo groot zijn dat ze geen namen hebben, alleen notaties.

Er zijn implicaties voor de echte wereld als P toevallig NP is (en weinigen dat we niet al leven als dat niet het geval is). Een voorbeeld van een dergelijk probleem is "Gegeven een afleverroute naar deze 100 locaties, wat de meest efficiënte route is om te nemen". Als je dat binnen een redelijke hoeveelheid tijd zou kunnen oplossen, zou je bezorgbedrijf (waarschijnlijk) 5% minder brandstof per jaar gebruiken. Op zijn beurt een korting van 5% op sommige grote carriers, en we zouden waarschijnlijk $ 1,50 / gallon benzine weer zien in de Verenigde Staten. En er zijn veel van dergelijke problemen. Computergraphics, meteorologische simulaties, veel van hen. P = NP heeft veel real-world science-fictiony implicaties (meestal met betrekking tot efficiëntieverbeteringen).

Maar ogenblikkelijk reizen naar verre locaties behoort daar niet toe.

    
antwoord gegeven 26.09.2012 / 14:41