Používá Douglas Adams 'Nekonečná nepravděpodobnost' odkazuje na P = NP?

7

Když jsem znovu probudil starý příspěvek P = NP , začal jsem si myslet: Je popis Douglas Adams objevování pohonu Nekonečná nepravděpodobnost pomocí použití zařízení s konečnou pravděpodobností, kde je P = NP použit k vyřešení problému? Je to jeho vysvětlení problému?

Můj bod, opakované vysvětlení: Je to moje vědomí, že "vědci" objevili konečnou možnost nepravděpodobnosti, nějakým algoritmem nebo porozuměním, které jim umožní dát správné parametry, a vyhnali konečnou improbablitu, věděli, že hádají, že pracují. Pak se pokoušeli najít stejnou cestu nekonečné nepravděpodobnosti, aplikovat algoritmus a vytáčet rukojeť.

Ale to trvalo příliš dlouho (to nebylo polynomiální čas, možná by to bylo N ^ p, p je pravděpodobnost), takže se vědci vzdali. Objevitel IID však použil disk Finite Improbability, aby odhadl řešení na libovolný algoritmus nebo rovnici a zahrnoval parametry, tj. Vyřešil ho jako problém P jako NP problém.

Na webu nemohu najít nic, co by o tom mohlo diskutovat, ale možná jsem něco nechtěl.

Je toto (nebo něco podobného), co Douglas Adams myslel s tímto popisem? Pokud ne, co to myslel?

    
dané AncientSwordRage 26.09.2012 12:02

4 odpovědi

7

Druh

Jeden způsob definování NP spočívá v tom, že otázka může být rozhodnuto v polynomiálním čase, kdy je přístup k nedeterminismu . Jak se ukázalo, nedeterminismus lze považovat za ekvivalent k tomu, že má počítač, který uspěje, pokud má nenulovou pravděpodobnost úspěchu. V podstatě je non-determinismus ekvivalentní k zařízení s konečnou pravděpodobností.

Takže danému zařízení, jako je zařízení s konečnou pravděpodobností, může být jakákoli nepravděpodobná událost pravděpodobná. Můžeme ji použít k vybudování počítače, který má přístup k nedeterminismu. Rozdíl mezi P a NP je pak neplatný, protože P a NP běží stejnou rychlostí na nedeterministickém počítači. Teoreticky jsou P a NP stále odlišné, ale rozdíl už není užitečný.

    
odpověděl 26.09.2012 21:58
7

Je vhodné poznamenat, že N v NP nelze použít jen na polynomiální problémy: Pokud je X zvláštní soubor problémů , o čemž lze rozhodnout v čase omezeném danou charakterizací je polynom pro P nebo exponenciální pro EXP pomocí Turingova stroje (DTM) , pak bude NX množinou problémů, o kterých může rozhodnout non-deterministická Turingův stroj (NTM).

Takže otázkou je, jak funguje FID. Musíte vyřešit problém, o kterém může rozhodnout DTM v polynomiálním čase pokaždé, když chcete skákat? Pokud jste postavili stroj, který používal FID k odstranění požadovaného non-determinismu z běhu TM, byste v podstatě vytvořili NTM. To má smysl, protože i když problémový prostor je (nebo spíše může být) nekonečný, jedna konkrétní instance problému je vždy konečná. Takže pravděpodobnost, že bude vždy "hádat" správně, je konečná. V tomto smyslu bude FID technologickým ekvivalentem k výpočtovému modelu NTM. Obecně platí, že ve vesmíru s FID neexistuje žádný praktický rozdíl mezi jakýmkoli X a jeho odpovídajícím typem problémů NX , ale bylo by stále neznámé, zda jsou skutečně stejné (jak jsou definováno přes TM, ne ID).

Nicméně nemá smysl argumentovat o celkové době běhu algoritmu, který zkracuje nekonečný vstup, stejně jako ve všech triviálních případech, které by byly nekonečné.

Pokud je IID jenom nějaký matematický problém, který jednou vyřešil, jen vám dá nějaký náhled na vybudování stroje, který provádí nějaký pohon, pak otázkou je, jak tvrdý je tento problém? Nemáme žádné náznaky, že by spadl do třídy NP - úplných problémů. Existuje tuna PSPACE (= NPSPACE ) problémů a ve skutečnosti dokonce i NEXPTIME . Pokud by bylo vaše pokročilé technologické FID pro vás PSPACE bez vašeho použití, tak byste čekali jen tak dlouho

Takže vztah mezi libovolnými X a NX by byl jako "pevný disk nepravděpodobnosti" a "konečný improbability drive". Zdá se, že jednotka nepravděpodobnosti nekonečné by spíše odpovídala stroji, který rozhoduje o každém problému v době konstanty bez ohledu na jeho složitost na DTM nebo NTM, protože nekonečně nepravděpodobné událost je v zásadě nikdy . Neexistují žádné takové události, které by se daly říci: Dokonce i dvě jaderné hlavice spontánně přeměňující se na misku petúnie a velice překvapivě vypadající spermie velryba není nemožná událost. Je to tak nepravděpodobné, že by se nikdo neobtěžoval dát varovné nálepky na takové hlavice.

Konečně odpovězte na svou otázku; Ne, nemyslím si, že Adams by udělal takovou pop-science chybu. Jeho křiklavé části (v nedostatečném termínu) jsou vždy záměrné a pracují ironičtěji. IID mírně připomíná problém s nedeterminismem, neboť dělá něco neuvěřitelně tvrdého, a to velkolepě účinným způsobem, stejně jako NTM. Ale tato podobnost je poměrně povrchní, jak jsem se snažil zdůraznit v předchozích odstavcích.

    
odpověděl 27.09.2012 02:27
3

Myslím, že byste mohli použít nekonečnou jednotku nepravděpodobnosti jako součást NP řešitele, který by činil P = NP.

Řekněme, že vyladíte svůj IID tak, že při náhodném výběru kandidátského řešení vám dává skutečné řešení. Podle definice je u problémů s NP poměrně snadné ověřit správnost řešení.

Hotovo.

Tvrdá část získává nekonečnou možnost nepravděpodobnosti.

    
odpověděl 26.09.2012 18:22
2

Nevidím, jak by tomu tak mohlo být. Velmi stručně, P a NP jsou dvě třídy výpočetních problémů. Problémy P mohou být řešeny v nějaké přiměřené době s dobře známými algoritmy. NP problémy jsou věřil (ale ještě nebyl prokázán) být takový, že jediný způsob, jak je vyřešit, je zkusit každé možné řešení v podstatě náhodně, dokud nezískáte správnou odpověď. Nicméně všechny problémy NP jsou podobné tak, že pokud zjistíte algoritmus, který vám umožní rychlejší vyřešení NP, tento algoritmus by se vztahoval na všechny ostatní problémy NP. Pokud jste se někdy dělali s matematikou, která ukazuje, kolik možných řešení existuje v prostoru řešení, možná uvidíte, proč to byla velká věc. Čísla v některých případech jsou tak velká, že nemají žádná jména, pouze zápisy.

Existují důsledky reálného světa, pokud se P stane rovnocenným NP (a málo, že ještě nejsme žijící, pokud to není). Například jedním z těchto problémů je "Vzhledem k tomu, že cesta pro doručení do těchto 100 lokalit je nejúčinnější cestou, kterou je třeba vzít". Pokud byste to mohli vyřešit v přiměřené době, vaše doručovatelská společnost by (pravděpodobně) využila o 5% méně paliva za rok. Na druhé straně snížíme o 5% z některých velkých přepravních vozidel a pravděpodobně bychom ve Spojených státech pravděpodobně viděli opět 1,50 USD / benzín. A existuje mnoho takových problémů. Počítačová grafika, meteorologické simulace, spousta z nich. P = NP má řadu reálných vědeckých fiktivních důsledků (většinou se zabývá efektivitou).

Ale okamžité cestování do vzdálených míst není jedním z nich.

    
odpověděl 26.09.2012 14:41

Přečtěte si další otázky týkající se značek