Gyorshir: P nem egyenlő NP ?
Augusztus hatodikán egy Vinay Deolalikar nevű matematikus szétküldött egy emailt, amelyben azt állítja, hogy megoldotta a P=NP problémát.
Ez a probléma a számítógéptudomány messze legfontosabb nyitott kérdése, és ha most elég gyors vagyok, a Vincent lesz az első olyan magyar blog, amelyben írunk erről.
Miről van szó? Egy döntési problémát úgy kell elképzelni, hogy valaki leír nekünk egy struktúrát, és arról el kell döntenünk, hogy megfelel-e bizonyos feltételeknek.
Példa. Megad valaki nekünk egy gráfot, aminek n csúcsa van, és el kell döntenünk, hogy kiszínezhetők-e a csúcsai három színnel úgy, hogy a gráfban ne legyen két, azonos színű szomszédos csúcs. Ez a probléma akkor van P-ben, ha van egy olyan programunk, amelynek a gráfok a lehetséges inputjai, és Q(n) lépés után megmondja nekünk, hogy a gráf 3-színezhető-e vagy sem. Itt a Q valamilyen polinom. Ezt nem tudjuk. (Én nem tudom, Deolalikar azt mondja, hogy ő tudja) . Amit tudunk, az az, hogy a probléma az NP osztályban van, azaz ha valaki azt állítja, hogy létezik 3-színezés, akkor azt polinomiális időben ellenőrizni tudjuk. Ez világos, hiszen minden csúcsnál megnézzük a szomszédos csúcsokat, és így n a négyzeten lépésben tudni fogjuk, hogy jó-e a a megadott színezés.
A P=NP probléma azt jelenti, hogy az NP (polinomiálisan ellenőrizhető) problémák P-k (azaz polinomiálisan megoldhatóak).
Számos problémáról sikerült bizonyitani, hogy NP teljes, azaz bármely NP probléma P-ben van, ha ő maga P-ben van (a fenti, 3-színezési probléma is ilyen).
Az NP osztály egyébként pontosan azokból a problémákból áll, amelyeket egy biológiai számítógép polinomiális időben meg tud oldani. Képzeljünk el egy baktériumot, amelynek a DNS-ében ott van a gráfunk, amiről el akarjuk dönteni, hogy kiszínezhető-e három színnel. A baktérium kiválaszt egy csúcsot a gráfban, és három részre osztja magát. Az első utód DNS-e a gráfot tartalmazza, de úgy, hogy a kiválasztott csúcs piros — a második utódnál kék, a harmadiknál zöld. Ezek után a három baktérium elindul, és kiválaszt egy új csúcsot. Ahogy a csúcshoz érnek, osztódnak. Az első utód első utódja a következő DNS-t fogja tartalmazni: az első csúcs piros, a második is piros. Az első utód második utódjában a második csúcs kék, az első utód harmadik utódjában a harmadik utód zöld. A szaporodó baktériumok sorban adják át utódaiknak az információt, és DNS-ükben átörökítik az addigi színezéseket. Ha egy baktérium DNS-e rossz színt kap, tehát szomszédos csúcsok azonos színűek lesznek benne, a baktérium elpusztul. Könnyen látható, hogy ha n idő múlva lesz még élő baktérium, a gráf 3-színezhető (és lesz olyan baktérium, amelynek a DNS-e tartalmazza a színezési információt).
Vinay Deolalikar azt állitja: bebizonyitotta, hogy P nem egyenlő NP-vel, tehát van olyan NP probléma, ami nem oldható meg polinomiális időben.
www.scribd.com/doc/35539144/pnp12pt
Ez a „preliminary version”. Belenéztem, valóban elég preliminary, de elvileg elképzelhető, hogy a végső bizonyitás jó (nagyon-nagyon kicsi esélyt látok rá). Alant olvasható Deolalikar emailje.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16517184-6ae1d16e8cb8e' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16517184&origin=www.orulunkvincent.hu&obj_id=192691293-16517184-6ae1d16e8cb8e&n=1' data-name='like-post-frame-192691293-16517184-6ae1d16e8cb8e' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>Dear Fellow Researchers,
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
Comments and suggestions for improvements to the paper are highly welcomed.
@regression: Igen, de a P-beliség elvi kérdés. Ha valami nem P-beli, akkor gyakorlatilag kezelhetetlen. Nyilván nem következik ebből, hogy ami P-beli, az kezelhető. Ellenben én úgy sejtem, nem nagyon van praktikus probléma, ami O(n^6)-nál nehezebb, és nem exponenciális. (A 6 csak hasraütés.) Biztos akad, de a kitevőben szereplő szám polinomiális problémák esetén úgy is felfogható nagyjából, mint az egymásba ágyazott ciklusok száma. Ha ez igen nagy, akkor valami gyanús.
@regression: Ott sem utasításokról beszélünk, hanem m#w kód az input, ahol m egy TG kódja, w pedig az ennek szánt input. Bebizonyítható, hogy az UTG lépéseinek száma felülről becsülhető legfeljebb a szimulált TG lépéseinek polinomjával.
@jotunder: Ezzel nem tudok egyetérteni, azzal viszont igen, hogy az ilyen problémák esetleg a közeljövőben (10-20 év) nem lesznek könnyen kezelhetőek, még ha P=NP igaz is. Viszont, ha P=NP igaz, akkor P=QP is, ami előrejelzi, hogy esetleg kvantumszámítógéppel jól kezelhetővé válnak ezek a problémák…
@egerészölyv: ennyi erővel a Pithagorasz-tétel repedezett pergamentekercsekre tartozik. Esetleg valami indokot tudsz mondani?
@jotunder: Igen, tudom. Olvastam cikkeket az NP!=QP témakörben, de ezek sem bizonyítások, csak erősebb-gyengébb sejtések.
@Ianas: Nem azt mondtam, hogy nincsen jelentősége, azt mondtam, hogy nem kell apokalipszist jósolni. Valaki feljebb idézte:
„If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. „
Mekkora baromság. Egyébként vannak még nehéz problémák az NP osztályon _kívül_ is.
@V8: Ebben igazad van, de nem mindegy, hogy valaki az unverzális gép, vagy a szimulált gép utasításait számolja. A rendező algoritmusok egy jelentős részénél például az összehasonlítások számát számolják. Sőt, a legritkább esetben adják meg ténylegesen egy klasszikus Turing gép kódját és lépésszámát. Ezt értettem „utasítás” alatt. Természetesen a végén a Turing gép lépései számítanak, ezért kell odafigyelni minden egyszerűsítésnél — erre akartam rávilágítani.
@regression: Vannak. 🙂 Sőt, vannak olyan problémák, amik a Turing-gép lehetőségei fölött állnak (en.wikipedia.org/wiki/Hypercomputation) 🙂
De az NP-nél nehezebb problémák valószínűleg emberi időben mérve kezelhetetlenek (és egyáltalán nem biztos, hogy érdemes kezelni őket… Talán a részgráf-izomorfizmus kivétel, azt titkosításhoz is lehetne használni, míg PSPACE-beli, ami nehezebb elvileg az NP-teljesnél.)
@V8: a srac osszekeveri a techonologiailag fejlettett az oktatas celjabol hasznossal. Remelem soha nem fog tanitani.
@regression: Nyilván nem adják meg, de a polinom/nem polinom kérdéskörben ez nem számít (és bonyolultságelméletileg UTG esetén az ő lépéseit kell számolni).
@Ianas: pontosabban az NP (és az NP-teljes) valódi részhalmaza PSPACE-nek. Egyébként a részgráfizo NP-teljes (NP-beli, mert egy adott hozzárendelés elég röviden leírható és helyessége poli időben ellenőrizhető, NP-teljességhez meg H-kört vissza lehet rá vezetni triviálisan).
@Ianas: „De az NP-nél nehezebb problémák valószínűleg emberi időben mérve kezelhetetlenek”
Helyesbítenék: egyes inputokra kezelhetetlenek. Az ördög mindig a részletekben van. A valóságban az inputok egy eloszlásáról van szó, és bizony ezekre gyakran van jó heurisztika.
Fordítva is van példa. Pl könnyen be lehet bizonyítani, hogy a SAT probléma esetén a legtöbb inputra egy egyszerű brute-force keresés O(logN) időben megtalálja a megoldást. Sajnos a gyakorlatban ennek semmi jelentősége nincs, mert általában azok a feladatok fordulnak elő a gyakorlatban, amire ez nem igaz.
Az már volt, hogy P=NP=PN=PINA?
@V8: Megint az a helyzet, hogy ugyanarról beszélünk. Nem arról beszélek, hogy az NP definíciók nem precízek, hanem arról, hogy oda kell figyelni
– minek a lépésszámát mérjük
– milyen az input formátuma
Tehát mégegyszer: nem a P NP definíciókat bírálom, csak megjegyeztem hogy egy eldöntési problémánál oda kell figyelni minden apró részletre, mert különben könnyű buta ellenpéldákat találni.
@V8: Nem, ez téves. Ahhoz, hogy NP-teljes legyen, ahhoz EZT kellene tudni visszavezetni egy másik NP-teljesre (pl. simán találhatsz EXPTIME problémát, amire „redukálható” valamely NP-teljes probléma, de attól nem lesz EXPTIME=NP.)
A másik oldal sem igaz: Nem NP-beli, mert ehhez nem elég az ellenőrizhetőség (hiszen egy tetszőleges, akár NP-teljesnél nehezebb problémánál is igaz lehet az, hogy ellenőrizhető P-ben egy helyes megoldás.)
@jotunder: De ezt a Némó kapitány témát még mindig nem értem 🙂
@Ianas: Van némi fogalmi zavar abban, amit írtál. Akkor leírom részletesen:
RGI (részgráfizo) probléma: input: G1 és G2 gráf
kérdés: van-e G1-gyel izomorf részgráf G2-ben?
Egy probléma NP-teljes, ha NP-beli és NP-nehéz.
NP-beliség (a tanú-tétel alapján): ha a válasz igen, akkor egy jó tanú G2-nek egy részgráfja, és ezen részgráf és G1 pontjai közötti izomorfia. Ez leírható legfeljebb O(G1+G2) méretben (G2 bizonyos pontjainak és éleinek felsorolása, meg a pontok egymáshozrendelésének felsorolása). Az ellenőrzés annyiból áll, hogy megnézzük, hogy a megadott részgráf tényleg részgráf-e G2-ben, és az izomorfia tényleg izomorfia-e (iszonyat buta implementációval is legrosszabb esetben négyzetes).
NP-nehézség:
Tétel: Ha L1 NP-teljes nyelv Karp-redukálható L2-re, akkor L2 NP-nehéz.
L1 itt legyen H-kör, L2 pedig RGI.
A Karp-redukció úgy fog kinézni, hogy G (n pontú gráf) eleme-e H-kör kérdést úgy alakítjuk át, hogy felveszünk egy n-pontú kört (legyen ez K), és megkérdezzük, hogy (K, G) eleme-e RGI. Helyesség:
=> ha G-ben van H-kör, akkor triviálisan K izomorf G egy H-körével.
<= ha K izomorf G egy részgráfjával, ez azt jelenti, hogy G-ben van egy n hosszú kör, tehát G-ben van H-kör.
A visszavezetés O(n) időben megvan, tehát ez egy jó Karp-redukció.
@Ianas: Viszont utánanéztem, és a részgráf-izomorfizmus valóban NP-teljes. A klikk-problémára lehet visszavezetni.
Egy igazi, NP-teljesnél nehezebb probléma pl. annak az eldöntése, hogy egy mondat beletartozik-e egy környezetfüggő nyelvbe.
@V8: A második rész nem világos. Abból, hogy egy konkrét esetben (H-kör) megmutatod, hogy az egy konkrét RGI típusú probléma, nem következik, hogy RGI NP teljes.
Mondok egy példát: meg kell keresned egy random 10 csúcsú gráfot egy 1000 csúcsúban. Ezt hogy vezeted vissza a Hamilton-kör keresésre polinom időben?
@Ianas: van neki egy tengeralattjárója. a mentális ujjlenyomatok elég erősek.
@jotunder: No, látod, pont itt veszítettem el a fonalat.
-Némó
-Nautilus
-Mentális ujjlenyomat
Van ennek a háromnak olyan részhalmaza, aminek elemei között maradéktalanul értem az összefüggést. De ez egy valódi részhalmaz 🙂
@Ianas: itt nem konkrét visszavezetésekről beszélünk, hanem az adott visszavezetés létezőségéről.
Nagyvonalakban:
NP-nehézség definíciója: egy nyelv NP-nehéz, ha tetszőleges NP-beli Karp-redukálható rá. Tudjuk továbbá, hogy a Karp-redukció tranzitív.
Így ha van egy NP-teljes L1 nyelvünk, akkor a definícióból következően tetszőleges NP-beli visszavezethető rá. Ha most L1-et visszavezetjük L2-re, akkor egy tetszőleges L3<L1 visszavezetés után meg tudjuk csinálni, hogy L3<L1<L2, és a tranzitivitás miatt L3<L2. Ez ábrán szebben látszana, remélem így is érthető.
Így elég megmutatni egy nyelvre „konstruktívan”, hogy NP-teljes (lásd pl Cook-Levin tétel SAT-ra), innentől kezdve elég egyedi visszavezetéseket csinálni. Attól, hogy nem tudok neked mondani egy konkrét visszavezetést, attól be tudom bizonyítani, hogy létezik 🙂
@V8: OK. Tényleg fáradt vagyok :D. Igazad van.
@jotunder: Tudom, hogy sántít a PDP-analógia, ezért is írtam, hogy „egyfajta” PDP. Ha az egész baktériumtenyészetet tekintjük „számítógépnek”, akkor az a példádban párhuzamosan processzál, nem? OK, szóval itt kizárólag Turing-gépek által megoldható feladatokról van szó, csak az a kérdés, milyen gyorsan oldják meg. Akkor a kérdésem lényege: ha tényleg igaz, hogy P=/=NP, akkor az azt jelenti, hogy bizonyos eldöntési problémákat Turing-géppel nem lehet ésszerű időn belül megoldani, hanem inkább olyasmivel, mint a PDP? Tudom, hogy ez laikus kérdés, de tudod, hogy nem vagyok matematikus, és úgy okul az ember, ha kérdez. 🙂
@tanarseged ur: bár nem engem kérdeztél, valami ilyesmiről van szó. A probléma viszont az, hogy jelenleg nem ismerünk (és nem úgy tűnik, hogy a közeljövőben fogunk) olyan (megvalósítható) eszközt, ami algoritmikus szempontból nem egy „hagyományos” Turing-gépnek felel meg. (OK, a kvantumszámítógép az pont ilyesmiről szól, de egyrészt azt nem igazán ismerem, másrészt nekem nem úgy tűnik, hogy az általánosan felhasználható lenne a közeljövőben).
Magyarul a P!=NP azt jelentené, hogy bizonyos problémákat tényleg nem tudunk értelmes időn belül megoldani, akármilyen erős számítógéppel sem. Nem mintha eddig meg tudtuk volna, de amíg nyitva van a P=NP lehetőség, addig lehet reménykedni 🙂 (Természetesen csomó NP-teljes problémára vannak közelítő algoritmusok, heurisztikák, akár pszeudopolinomiális algoritmusok, ilyeneket szokás kutatni és alkalmazni is.)
@tanarseged ur: A PDP praktikusan Turing-gép. A szaporodó baktériumos modell is csak akkor oldja meg a dolgot, ha elegendően sok erőforrás van, de könnyen belátható, hogy egy viszonylag kisebb gráf 3-színezéséhez is tonnákban mérhető táptalaj kellene.
A kvantuminformatika jelent majd némi megoldást.
@V8: A kvantumszámítógép teljesen ekvivalens a Turing-géppel, vagyis kölcsönösen képesek szimulálni egymást. (Ha nem így lenne, akkor belátható időn belül lehetne olyan gépet készíteni, amelyik megoldja pl. a megállási problémát.)
Olvastam olyan elméleti tanulmányt, hogy egyes speciális kvantumszámítógépek erősebbek lehetnek a Turing-gépnél, de ezek olyan feltételekre támaszkodnak, amelyek nem biztos, hogy fizikailag kivitelezhetőek (pl. mert a fizika törvényei erősebb korlátokat támasztanak.)
@Ianas: kifejezőerőben ekvivalens, én lépésszámról beszéltem. Ugyanúgy, ahogy a determinisztikus és nem determinisztikus TG is ugyanazokat a nyelveket tudja felismerni, de ha P!=NP, akkor az NDTG gyorsabban (persze ez nem egy precíz megfogalmazás, de kb ez a lényege).
@V8: Köszönöm.
„A probléma viszont az, hogy jelenleg nem ismerünk (és nem úgy tűnik, hogy a közeljövőben fogunk) olyan (megvalósítható) eszközt, ami algoritmikus szempontból nem egy „hagyományos” Turing-gépnek felel meg.”
Az élő idegrendszer majdnem ilyen, nem? 🙂 OK, az tényleg nem „implementálható” – egyelőre?
@Ianas: „A PDP praktikusan Turing-gép.”
Bevallom, ezt nem értem. Úgy homálylik, hogy a Turing-gép egyszerre csak egy műveletet végez, a PDP pedig egyszerre sokat. Rosszul tudom? Persze lehet olyan programot írni, amelyik szimulál egy tanuló hálózatot, és lefuttathatom a számítógépemen, de valójában a gépem belsejében szekvenciális feldolgozás zajlik, és nem párhuzamos.
@tanarseged ur: az idegrendszer kicsit más téma, ebben nem vagyok otthon. Jelenleg legfeljebb elég primitív és kis komplexitású utánzatokat lehet gyártani.
Az ekvivalens azt jelenti itt, hogy pontosan ugyanazokat a feladatokat tudja megoldani. Tehát ha egy feladatra tudok csinálni egy TG-t, akkor tudok egy PDP-t is, és ez fordítva is igaz. A futásidő más kérdés. Egyébként a gyakorlatban ez azért nem használható, mert attól, hogy párhuzamosan tudsz dolgozni, az energia, hely, stb igény ugyanúgy exponenciálisan nő.
@tanarseged ur: A PDP szimulalhato Turing gepen, nem problema. A szimulacio futasi ideje lesz lenyegesen hosszabb a szimulacioval.
Valojaban eljarast nehez elkepzelni altalanosabbat mint a Turing gepen valo kiszamithatosag. Az elo idegrendszer egy Turing gep (feltetelezzuk a hozzaferest hosszu kulso memoriaszalagokhoz). Az, hogy nem bonyolultabb mint a Turing gep az kovetkezik abbol, hogy minden apro reszlete modellezheto, hogy nem egyszerubb az pedig abbol, hogy en ezt most ideirom.
@jotunder: Azért halványan megjegyzem, hogy ez korántsem lefutott meccs. Ha Penrose-nak igaza van, akkor
1.) A tudatban erőteljes kvantummechanikai jelenségek zajlanak
2.) Ezek mögött „nem-kiszámítható” (vagyis TG-nél erősebb) folyamatok állnak a háttérben.
Ebben az esetben lehet, hogy a tudat „több”, mint egy Turing-gép (bár én ezt némiképp túlzónak tartom, mindenesetre kiváló táptalaj lehet egy már-már vallásos töltetű vitához.)
@jotunder: Azt tudom, hogy szimulálható. Azt nem tudom, hogy matematikus szemmel van-e különbség az alábbi két állítás között:
(1) X mechanizmus egy Turing-gép.
(2) X mechanizmus szimulálható Turing-géppel.
A futási idő lehet, hogy matematikai szempontból nem különbség (nem tudom), de pl. egy állat számára mondjuk egy ragadozó- vagy prédafelismerő „program” futási ideje már élet-halál kérdése.
„Az elo idegrendszer egy Turing gep” – de hát nagyon sok problémát gyakorlatilag PDP-vel old meg. Tehát nem két különböző eset-e az, hogy
(3) Turing-gép,
vagy
(4) szimulálható Turing-géppel?
Vagy ez matematikai szempontból mindegy?
Megjegyzem, milyen szépen megcáfolódott a tőlem származó 2. komment burkolt sejtése: volt Index-címlap, mégis elmaradtak az ezzel járó kellemetlenségek. És mennyivel jobb is, mint egy n+1-edik politikai marhaság. Több ilyen posztot! 🙂
@tanarseged ur: Nevezd gépnek azokat a mechanizmusokat amelyek egy számhoz hozzárendelik a természetes számok egy végtelen részhalmazát. Tehát inputként bemegy mondjuk a tíz és kijönnek a prímszámok. Nem tudod egészen pontosan mi van a gép belsejében, azt tudod értelmezni, hogy a gép egy végtelen részhalmazt kiad. A következő módon teszi, minden számról sorban eldönti, hogy benne van-e a halmazban vagy sem. A papíron meg fog jelenni egy olyan sorozat, hogy egy igen, kettő nem, három nem, négy igen,…..
Néha nagyon sokat fog várni a gép, bizonyos inputokra esetleg bajba kerül, tehát egy adott számon végtelen sok ideig gondolkozik, de a lényeg az, hogy bemegy egy szám, és az a szám valahogy „programozza” a gépet, hiszen tudod, hogy egy valami véges mechanizmus van a gépben. Amikor azt mondom, hogy véges, akkor úgy képzelem el, hogy a doboz véges, de esetleg egy végtelen hosszú szalag van a géphez mellékelve amelyre időnként adatokat ír ki. Konkrétan így képzelsz el egy számítógépet. Mondhatod persze, hogy de azt nem számokkal programozzák, ám ez nem érdekes, mert a számok és a programok kölcsönösen megfeleltethetők. Gondold végig, Shakespeare Hamletje leírható egy számmal, nevezetesen azzal a számmal ami bináris számrendszerben a morse kódja. Ugyanez bármilyen véges programra is igaz.
Felteszed, hogy a gép ugyanarra az inputra mindig ugyanazt írja ki, nincs benne semmiféle ordenáré kvantummechanikai trükk.
Egy gép bonyolultságát a részhalmazok családja méri, amelyeket képes kiírni. Nincs olyan mechanizmus ami több részhalmazt tud kiírni mint egy Turing gép. Egészen pontosan azt hívjuk Turing gépnek ami
azt tudja kiiírni mint egy sztenderd számítógép.
Megkérdezheted, hogy van-e olyan részhalmaz amelyet a gép nem tud kiírni. Igen van, mert kevesebb szám van mint részhalmaz. Más kiírási definiciók is vannak, de a Turing gépet ebből lehet megérteni. A legbonyolultabb mechanizmus ami elképzelhető.
@tanarseged ur:
(1)-re inkább azt mondanám, hogy X konstrukció ekvivalens egy TG-vel. Ez kb azt jelenti, hogy X szimulálható egy TG-vel, és egy TG szimulálható X-szel.
(2) értelemszerűen gyengébb dolog, pl egy egyszerű véges automata is szimulálható TG-vel, de egy TG nem szimulálható egy véges automatával.
Ezek a fogalmak egyébként a kifejezőerőre vonatkoznak, a lépésszámok itt (általában) irrelevánsak.
@jotunder: Az idegrendszer inkább a fordítottja: bemegy egy praktikusan végtelenül bonyolult input (ha az élőlény által észlelhető utolsó falevél erezetét, az utolsó sündisznó tüskéinek számát, a levegőben kószáló utolsó feromonmolekulát, stb-t is belevesszük, akkor az praktikusan végtelen), és outputként kijön egy szám, azaz egy diszkrét viselkedés – az állat mondjuk eszik, iszik, támad, menekül, üzekedik, elbújik, stb., mindegyiket megjelölhetjük egy számmal (funkció szerint, mert persze mindegyiket lehet sokféleképpen is csinálni, de akár az alváltozatokat is megkülönböztethetjük számokkal). De ha jól értem, akkor mivel a PDP szimulálható TG-vel, nem minősül bonyolultabbnak? Sőt, akár másnak? Akkor a futási idő nem számít? Ezt azért nem értem, mert a „P ? NP” probléma viszont végül is ugyancsak a futási időről szól, nem? Akkor mi következne abból, ha kiderülne, hogy „P != NP” ?
@tanarseged ur: ez egy igen jó kérdés.
Amennyire értem a dolgot, a bizonytalanság a különbség. Nemdet automatát lehetséges (sok) det automatával szimulálni, de akkor nincs biztos felső határa a lépésszámnak. Senki nem garantálja ugyanis, hogy előbb-utóbb a sok det részautomata közül tényleg kiválasztódik a megfelelő.
@tanarseged ur: @peetmaster:
pontosabban egy NDTG-t lehet egy TG-vel szimulálni, és biztos felső korlát is van a lépésszámra: ha az NDTG poli időben végez, akkor a TG exp időben.
A probléma, hogy a TG egy létező konstrukció, míg NDTG-t nem tudunk csinálni (vagyis a kvantumszámítógép vmi ilyesmi lehetne).
Tehát itt két fogalom van:
– egy módszer/automata kifejezőereje, amiben a TG, NDTG, PDP, stb stb mind ekvivalens — ez azt jelenti, hogy milyen problémák megoldása lehetséges vele elvileg,
– és egy adott kifejezőerővel rendelkező módszerek/automaták sebessége bizonyos feladattípusokra
A TG-vel felismerhető nyelveken belül az NP nyelvosztály csak egy (valódi) részhalmaz, de igazából ezen kívüli problémák a gyakorlatban ritkán jönnek elő. A P!=NP annyit jelentene, hogy TG-vel (lényegében az összes létező számítógép az) polinom időben tényleg nem tudunk megoldani egy csomó problémát, és nem csak mi vagyunk „bénák”, amiért eddig nem sikerült.
A P?NP kérdéskörön kívüli dolog, hogy ha képesek lennénk csinálni egy NDTG-t, akkor simán meg tudnánk polinom időben oldani minden NP-beli problémát függetlenül attól, hogy P és NP viszonya micsoda.
Természetesen vannak olyan problémák, amiket garantáltan nem lehet megoldani polinom időben TG-vel (ettől még egy részüket simán meg lehet oldani exp vagy annál is rosszabb időben), és vannak olyanok is, amik algoritmikusan eldönthetetlenek (RE-be tartoznak, de R-be nem), és olyanok is, amik TG-vel egyáltalán nem megoldhatók (pl diagonális nyelv felismerése).
@tanarseged ur: V8 már leírta. Ez nem a kiszámíthatóságról szól, hanem a futási sebességről.
@tanarseged ur: Ha a Turing gép lépésszámát nem a természetes számokkal, hanem a megszámlálható rendszámokkal paraméterezzük (tehát pl. megengedhető, hogy egy számot összevessen az összes természetes számmal), akkor egy erősebb osztályt kapunk. Ebben az esetben is van értelme a P=NP-nek, az omega az omega-adikon rendszámnál kevesebb lépést futó algoritmus a P. És itt tudják, hogy nem egyenlő a két osztály, sőt majdnem mindent tudnak amit tudni lehet, és ez az amiben a Deolalikar is résztvett, de ez egyszerűen minőségileg más kérdés.
Ma egyébként az Abel díjas Varadhan feltett egy preprintet a netre, amiben az Erdős Rényi véletlen gráfok nagy eltérés tételeit írja le (Varadhan a nagy eltérés tételek atyja). Az egész cikk a Lovász és társszerzői által leírt limeszelméleten nyugszik. Számomra ez sokkal érdekesebb mint a Deolalikar rossz cikke, de mégse írhatok róla posztot. A Barabasi elméletről talán fogok írni, kicsit nagy munka, és kicsit kevés az időm.
michaelnielsen.org/polymath1/index.php?title=Immerman%27s_letter
ez egyelore a vegso szo.
ez kimaradt: xkcd.com/287/