A Douglas Adams használja az „Infinite Improbability” -et P = NP-re?

7

Miután csak újra felkeltette a régi P = NP bejegyzést, elkezdtem gondolkodni: Douglas Adams leírása a Végtelen Hihetetlen meghajtó felfedezésének a véges, valószínűtlen eszköz használatával való leírása, ahol P = NP-t használnak a probléma megoldására? Ez a probléma magyarázata?

Az én pontom, újra elmagyarázta: Megértettem, hogy a „tudósok” felfedezték a végtelen valószínűtlenséget, valamilyen algoritmussal vagy megértéssel, amely lehetővé tette számukra a megfelelő paramétereket, egy matematikai fogantyút hajtva és kijöjjön a végtelen improbablitás meghajtóról, tudták a találgatásról. Aztán megpróbálták ugyanolyan módon megtalálni a végtelen valószínűtlen meghajtót, alkalmazni egy algoritmust és forgatni a fogantyút.

De ez túl sokáig tartott (nem polinomiális idő volt, talán N ^ p, a p pedig a valószínűsége), így a tudósok lemondtak. Azonban a IID felfedezője a véges nem-hihetetlen meghajtót használta fel arra, hogy kitalálja a megoldást bármilyen algoritmusra vagy egyenletre, és az érintett paraméterekre, azaz P-problémaként NP-problémaként oldotta meg.

Nem találok semmit a webről, amely erről beszélt, de talán hiányoztam.

Ez az (vagy valami hasonló), amit Douglas Adams jelentett ezzel a leírással? Ha nem, mit értett?

    
készlet AncientSwordRage 26.09.2012 12:02
forrás

4 válasz

7

Rendezés.

Az NP meghatározásának egyik módja, hogy a kérdés a polinomidőben határozható meg, hozzáféréssel a nem determinismához . Mint kiderül, a nem-determinizmus úgy tekinthető, hogy egyenértékű egy olyan számítógéppel, amely sikeres, ha nem-nulla valószínűséggel sikerül. Lényegében a nem determinizmus egyenértékű a véges valószínűségi eszközzel.

Így egy olyan eszköz, mint egy végtelen valószínűtlen eszköz, bármilyen valószínűtlen esemény valószínűsíthetővé válik. Ezt használhatjuk olyan számítógép létrehozására, amely hozzáférést biztosít a nem determinisztához. A P és NP közötti megkülönböztetés akkor vitatott, mert a P és az NP ugyanolyan sebességgel futnak egy nemdeterminista számítógépen. Elméletileg P és NP még mindig különböznek, de a különbség már nem hasznos.

    
válasz adott 26.09.2012 21:58
forrás
7

Érdemes megjegyezni, hogy a N -es NP -es számot nem csak a polinomiás problémákra lehet alkalmazni: Ha a X egy bizonyos problémacsoport , amely egy adott jellemzés által meghatározott időben határozható meg ( az determinisztikus Turing gép (DTM) által használt polinom P vagy exponenciális EXP számára, majd NX lesz a nem determinisztikus által megoldható problémák halmaza Turing Machine (NTM).

Tehát a kérdés az, hogy a FID valóban működik. Meg kell oldania egy olyan problémát, amelyet egy DTM-el lehet eldönteni, ha minden alkalommal ugrik? Ha olyan gépet épített, amely az FID-t használja a szükséges nem determinizmus eltávolításához a TM futásából, lényegében NTM-et épített volna. Ez valójában van értelme, mert bár a problématerület (vagy inkább lehet) végtelen, a probléma egy konkrét példája mindig véges. Tehát a valószínűség, hogy mindig "találgatni" helyesen, véges. Ebben az értelemben az FID az NTM számítási modelljéhez hasonló technológiai egyenértékű lenne. Tehát általában egy FID-ben lévő univerzumban nincs gyakorlati különbség a X -es és a megfelelő NX -es osztálycsoportja között, de még mindig nem ismert, hogy valóban egyenlőek-e (ahogyan a TM-eken, nem pedig az ID-eken).

Ugyanakkor nincs értelme vitatkozni egy végtelen bemenetet lebontó algoritmus teljes futási idejéről, mint az összes, de néhány végtelen eset esetében is.

Ha az IID csak egyfajta matematikai probléma, akkor ha egyszer megoldott, csak néhány betekintést ad, hogy építsen egy gépet, amely valamilyen meghajtást hajt végre, akkor a kérdés az, hogy milyen nehéz ez a probléma? Semmi sem utal arra, hogy az a NP -es teljes osztályba sorolható. Van egy tonna PSPACE (= NPSPACE ) probléma, és még NEXPTIME is. Ha PSPACE volt, akkor a varázslatos fejlett technológiai FID nem lenne hasznos számodra.

Tehát a X és a NX között fennálló kapcsolat olyan lenne, mint a "rögzített valószínűtlen meghajtó" és a "véges valószínűtlen meghajtó". Úgy tűnik, hogy a végtelen valószínűtlen meghajtó inkább egy olyan gépnek felel meg, amely a állandó idő alatt minden egyes problémát eldönti, függetlenül attól, hogy a DTM-en vagy NTM-en bonyolult-e. az esemény alapvetően az, amit soha nem fog megtörténni. Ilyen esemény nem merülhet fel: Még két nukleáris robbanófej is, amely spontán transzformálódik egy petunias tálba és egy nagyon meglepett, sperma bálna, nem lehetetlen esemény. Csak annyira valószínűtlen, hogy senki sem zavarja, hogy figyelmeztető matricát helyezzen az ilyen fejjel.

Végül válaszoljon a kérdésére; Nem, nem hiszem, hogy Adams egy ilyen pop-tudományi hibát követett volna el. Wibbly-wobbly részei (a jobb kifejezés hiányában) mindig szándékosak és ironikusabbak. Az IID kissé emlékeztet minket a nem determinisztikus kérdésre, mivel látványosan hatékony módon csinál valamit, ami bosszantóan nehéz, ahogyan egy NTM is. De ez a hasonlóság meglehetősen felületes, ahogy megpróbáltam rámutatni az előző bekezdésekben.

    
válasz adott 27.09.2012 02:27
forrás
3

Úgy gondolom, hogy használhat egy végtelen valószínűtlen meghajtót egy NP-megoldás részeként, ami P = NP-t eredményezne.

Mondja el, hogy hangolja be az IID-t úgy, hogy véletlenszerűen kiválasztva egy jelölt megoldást, megadja a tényleges megoldást. Definíció szerint az NP problémák esetében a megoldás helyességének ellenőrzése viszonylag egyszerű.

Kész.

A kemény rész a végtelen valószínűtlenség meghajtót kapja.

    
válasz adott 26.09.2012 18:22
forrás
2

Nem látom, hogy ez hogyan történhet. Röviden, P és NP két számítási problémás osztály. A P-problémákat ésszerű időn belül jól ismert algoritmusokkal lehet megoldani. Az NP-problémákat úgy vélik (de még nem bizonyították), hogy azok megoldásának egyetlen módja az, hogy minden lehetséges megoldást lényegében véletlenszerűen próbáljunk meg, amíg nem kapjuk meg a helyes választ. Azonban az összes NP-probléma hasonló ahhoz, hogy ha egy olyan algoritmust fedeztek fel, amely lehetővé tette, hogy gyorsabban megoldhasson egy NP-t, akkor ez az algoritmus minden más NP-problémára vonatkozik. Ha valaha is a matematikával bukkantál fel, amely megmutatja, hogy hány lehetséges megoldás létezik a megoldás-térben, akkor láthatod, miért volt ez egy nagy ügy. Számos olyan szám, amely olyan nagy, hogy nincsenek nevük, csak jelölések.

Valódi világ következményei vannak, ha P egyenlő NP-vel történik (és kevés, hogy még nem élünk, ha nem). Például az egyik ilyen probléma az, hogy „a 100 helyszínre szállítmányozási útvonalat adunk, ami a leghatékonyabb útvonal. Ha ezt ésszerű időn belül megoldaná, a szállítási vállalat (valószínűleg) évente 5% -kal kevesebb üzemanyagot használna. Ezzel 5% -os csökkenést jelentett néhány nagy fuvarozó flottától, és valószínűleg ismét 1,50 dollár / gallon benzint fogunk látni az Egyesült Államokban. És sok ilyen probléma van. Számítógépes grafika, meteorológiai szimulációk, sok közülük. P = NP sok valós tudomány-fantasztikus következménygel rendelkezik (többnyire a hatékonysággal foglalkozik).

A távoli helyekre történő pillanatnyi utazás azonban nem az egyik.

    
válasz adott 26.09.2012 14:41
forrás

Olvassa el a címkéken szereplő egyéb kérdéseket