9.3. A szóprobléma - rekurzív és rekurzívan felsorolható nyelvek

A 0-típusú nyelvek esetén a wL reláció általában algoritmikusan nem eldönthető. Ez a fejezetezt a problémakört vizsgálja meg részletesebben. (Lásd a A Turing-gépek megállási problémája és az algoritmikusan eldönthetetlen feladatosztályok kapcsolata fejezetet is.)

Egy L nyelvet rekurzívnak nevezünk, ha a wL tartalmazásiprobléma algoritmikusan eldönthető.

Egy L nyelvet rekurzívan felsorolhatónak nevezünk, ha van olyan eljárás, amely az összes wL szót valamilyen sorrendben (esetleg ismétlésekkel) felsorolja.

12. Megjegyzés. Minden rekurzív nyelv nyilván rekurzívan felsorolható. Nem kell ugyanis mást tennünk, mint rendre megvizsgálni az összes wT * szót alkalmazva rájuk az eldöntési algoritmust, és egy w szót beleveszünk a felsorolásba, ha igen választ kapunk, egyébként elhagyjuk.

75. Tétel. Egy L nyelv akkor és csak akkor rekurzív, ha mind az L mind az rekurzívan felsorolható.

Bizonyítás. Ha L rekurzív, akkor a wL probléma algoritmikusan eldönthető, akkorugyanez áll az nyelvre is, hiszen wL akkor és csak akkor teljesül, ha w. Eszerint ugyanazt az eldöntési algoritmust használhatjuk az - re, azzal a különbséggel, hogy amit L esetén elfogadtunk azt most nem, és fordítva.

Másik irány: Tegyük fel, hogy mind az L mind az rekurzívan felsorolható. Kombináljuk az L és az felsorolását biztosító eljárásokat úgy, hogy váltakozva hol az egyikkel, hol a másikkal állítunk elő egy-egy szót, miáltal egy olyan w 0, w 1, … felsorolást kapunk, ahol w 2i L, w 2i+1 minden i=0, 1, 2… értékre. Mivel afelsorolás teljes, ezért a w keresett szónak valahol elő kell fordulnia, ígycsak azt kell eldöntenünk, hogy páros vagy páratlan pozícióban fordul-e elő, így tulajdonképpen egy döntési algoritmust adtunk meg az L- re.∎

76. Tétel. Minden 1-típusú nyelv rekurzív, és minden 0-típusú nyelv rekurzívan felsorolható.

77. Tétel. Van olyan rekurzív nyelv, amely nem 1-típusú.

Bizonyítás. Minden 1-típusú nyelvtant megadhatunk úgy, hogy felsoroljuk a szabályait. Feltehetjük, hogy a nyelvtanban terminálisok csak A → a alakú szabályban fordulnak elő ( AN, aT ). A nemterminális ábécét a szabályok implicit módon definiálják. Ezek után tekintsük azt az 1-típusú nyelvtant, amelynek terminális ábécéje T={0, 1}. Kódoljuk a nemterminális jeleket a 01, 011, 0111, … jelsorozatokkal, ahol az S kezdőszimbólumnak mindig a 01 kód feleljen meg. Kódoljuk továbbá a 0 és az 1 terminális jeleket 00 és 001 szavakkal, a  → és a # (elválasztó-) jeleket 0011, illetve 00111 szavakkal. Ezek alapján minden nyelvtant kifejezhetjük egy {0, 1}*- beli szóval. Rendezzük az összes {0, 1}*- beli szót valamilyen módon (ezzel a nyelvtanokat is sorbarendeztük).

Legyen w i a {0, 1}* megadott rendezés értelmében az i- edik eleme a {0, 1}*- nak és definiáljuk az L nyelvet úgy, hogy

L={w i | w i L(G i )}

ahol G i az i- edik nyelvtant jelenti. Az L nyelv rekurzív, mert a wL véges sok lépésben eldönthető. Ugyanis egy adott w- ről eldönthetjük, hogy hányadik eleme a rendezett halmaznak. Legyen ez i, akkor meghatározzuk a G i - t, ami úgy történik, hogy rendre előállítjuk a {0, 1}*- beli szavakat (célszerűenugyanabban a rendezési sorrendben, mint amit az előbb használtunk), és mindegyikről egyenként eldöntjük, hogy ez a kódolás megfelel-e egy 1-típusú nyelvtannak vagy sem. Ez szintén megtehető véges lépésben. Miután meghatároztuk a G i - t, eldönthetjük, hogy wL(G i ) teljesül-e, ami szinténvéges számú lépésben megtehető.

Most belátjuk, hogy L nem 1-típusú. Ha ugyanis az volna, akkor volna egy olyan G j a fenti felsorolásban, amelyre L=L(G j ). Tekintsük a {0, 1}* j- edik elemét, amit w j - vel jelöltünk. Ha w j L(G j ), akkor az L definíciója értelmében w j L=L(G j ) ami ellentmondás. Ha w j L(G j ), akkor w j L=L(G j ) szintén ellentmondás, tehát L nem 1-típusú.∎

78. Tétel. A rekurzívan felsorolható nyelvek osztálya megegyezik a 0-típusú nyelvek osztályával.

Az angol Recursively Enumerable név alapján jelöljük e nyelvosztályt RE-vel.

Amint láttuk a Turing gépek leírása rekurzívan felsorolható, vagyis csak megszámlálhatóan végtelen sok Turing gép, és ennek megfelelően megszámlálhatóan végtelen sok rekurzívan felsorolható nyelv létezik.

Ugyancsak megszámlálhatóan végtelen sok szót tartalmaz T * bármilyen véges, nemüres T esetén.Ezzel szemben egy megszámlálhatóan végtelen halmaz lehetséges részhalmazainak száma nem megszámlálható végtelen, hanem több annál.

Tehát egy adott T ábécé feletti nyelvek száma több, mint ahányat Turing-géppel el lehet fogadni;vagy érdekesebben hangzó megfogalmazással: több, mint amennyit fel lehet sorolni.

Ezek alapján az itt tárgyalt nyelvosztályokra a következő hierarchia teljesül:

C SRR EA L,

ahol C S a környezetfüggő nyelvek, R rekurzív nyelvek, R E a rekurzívan felsorolható nyelvek osztálya, A L pedig az összes nyelv osztályát jelenti.

Itt emlékezzünk vissza arra, hogy a jegyzet elején tárgyalt Markov-féle algoritmus (lásd Markov-féle normál algoritmus) ugyancsak univerzális számítási modell, vagyis minden rekurzívan felsorolható nyelv elfogadtatható ilyen algoritmusokkal, és mivel formális modellről van szó, pontosan ezek fogadtathatóak el ily módon.

9.3.1. Bonyolultsági osztályok

Tehát a rekurzív függvények, illetve rekurzív nyelvek osztálya megadja a kiszámíthatóság határát, az ezen kívül eső függvények, illetve nyelvek esetén nem garantált, hogy valaha is befejeződik a számítás egy adott inputra és megáll a Turing-gép.

Viszont a rekurzív osztályon belül sem egyformák a problémák, vannak amelyek egyszerűen megoldhatóak, és vannak amelyek bonyolultak. Ebben az alfejezetben röviden áttekintjük a legfontosabb bonyolultsági fogalmakat.

Ha TM egy determinisztikus Turing-gép, vV k input (vagyis vV * és |v|=k ), a számítás időigényének a t T M (v) függvényt nevezzük, mely a következő alakú:

t T M (v)=max{n, |v|)}=max{n, k}, ha TM a v inputon n lépésután megáll, egyébként pedig ∞.

Egy konkrét számítási folyamat időigényének meghatározása után olyan időigény-fogalmat vezetünk be, amely egy egész problémára, és nem csak annak egyes példányaira vontkozik. Az időigényt a bemenet hosszának függvényében fogjuk megadni.

Azt mondjuk, hogy egy determinisztikus TM Turing-gép időigénye (legfeljebb) f(n), ha TM futási ideje egyetlen n hosszú bementre sem több f(n)- nél. Ha egy f(n) időigényűTuring-gép elfogad egy L nyelvet,akkor azt mondjuk, hogy LT I M E(f(n)).

T I M E(f(n)) egy bonyolultsági osztály, ami tartalmazza azokat a nyelveket, amelyek f(n) időben eldönthetőek.

Formálisan tehát a TM Turing-gép időbonyolultsága (maximális időbonyolultsága):

t T M (n)={t T M (w), ahol |w| ≤ n}.

A tárbonyolultság a számítások közben a szalagokon előforduló leghosszabb sztring hossza (vagyis a nem szóköz jelek száma).

Az eddig itt tárgyalt Turing-gépek determinisztikus működésűek (ahogy napjaink számítógépei is azok).

A Turing-gépeknek a nemdeterminisztikus verzióját is említettük már. A nemdeterminisztikus verzióban a d "függvény" tulajdonképpennem egyértelműen adja meg az új állapot, új szalagjel, fejmozgás hármas(oka)t (vagyis a d a Q×V×{B a l, J o b b, H e l y b e n} halmaz részhalmazaiba képez).Itt a kiszámíthatóságot úgy definiáltuk, hogy van olyan számítási sorozat amely az eredményt szolgáltatja.

Számítási "erejét" tekintve a nemdeterminisztikus verzió sem tud többet a determiniztikus változatoknál, vagyis minden ami nemdeterminisztikusan kiszámítható kiszámítható determinisztikusan is. (A másik irány triviális.) A nemdeterminisztikus változat számítási sebessége, hatékonysága viszont lehet jobb a determinisztikusénál. Ez azt jelenti, hogy pl. "találgatással" hamarabb találhatunk megoldást. A következő részben röviden kitekintünk arra, hogy milyen problémák milyen költséggel oldhatók meg determinisztikus, illetve nemdeterminisztikus Turing-gép segítségével.

A továbbiakban néhány fontos bonyolultsági osztályt említünk meg. A bonyolultsági osztályok meghatározásához szükségünk lesz a számítási módra, amely lehet determinisztikus vagy nemdeterminisztikus. Ezenkívül arra, hogy mely erőforrást (idő, tár: szalag) korlátozzuk.

Mint az előző részben bevezettük, a determinisztikus módon, f(n) időkorlátozással számolóTuring gépekkel kiszámítható nyelvek a T I M E(f(n)) bonyolultsági osztályt alkotják.Általában az f(n) nemnegatív egészekhez nemnegatív egészeket rendelő függvénytől megköveteljük, hogy monoton növekvő legyen. Ha f(n)=c egy c∈ℕ konstansra, akkor a nyelv bármely v szavátmaximum |v|+c lépésben eldönti a TM Turing-gép. Szokásos a lineáris függvény( f(n)=c n ), illetve az n tetszőleges polinómjának használata(ahol n a bemeneti szó hossza).Azon nyelvek (problémák) unióját, amelyekhez van olyan determinisztikus Turing-gép, ami ezek szavait valamilyen polinomfüggvénnyel megadható időben eldönti (kiszámítja), P bonyolultági osztálynak nevezzük.

Legyen most TM egy nemdeterminisztikus Turing-gép. Azt mondjuk, hogy TM f(n) időben eldönti/felismeri az L nyelvet, ha bármely vL szóval indítvaa kezdőkonfigurációból van olyan számítás, amely elfogadja v- t legfeljebb f(n) lépés után ( n=|v| ).

Azon nyelvek unióját, amelyekhez van olyan nemdeterminisztikus Turing-gép, ami a ezek szavait valamilyen polinomfüggvénnyel megadható időben eldönti (kiszámítja), NP bonyolultági osztálynak nevezzük.

A számítógéptudomány egyik legfontosabb nem tisztázott problémája a P és NP bonyolultsági osztályok viszonyának eldöntése, vagyis mivel P ⊆ NP, ezért a kérdés P≡?NP alakba írható. Általában elfogadott az a feltételezés, hogy a két osztály nem egyezik meg, egyelőre azonban nem ismert olyan feladat (nyelv) ami NP-ben van és bizonyítottan nincs P-ben.

Minden NP-beli nyelvre (problémára) igaz, hogy minden szavára létezik egy "tömör bizonyíték" (ami polinomiális időben ellenőrizhető) arra, hogy az adott szó benne van a nyelvben.

Az NP osztály rengeteg természetes és a gyakorlatban is fontos számítási problémát tartalmaz. Például sok tervezési probléma (utak, kiértékelések, egyenletek megoldásai, VLSI tervrajzok) ilyen. Amikor optimális (egy adott feltételt kielégítő) megoldást keresünk, akkor a keresett objektum maga lesz a bizonyíték. Ezek a bizonyítékok gyakran fizikai objektumok vagy azok matematikai absztrakciói, amelyek nem túl nagyok a probléma méretéhez képest és a feltételek is gyakran polinomiális időben ellenőrizhetőek. Azokat a problémákat nevezzük NP-teljesnek, amelyek legkevésbé feltételezhetőek, hogy egyben P-beliek is. Egy L problémát NP-teljesnek nevezünk, ha abból, hogy L∈ P az következik, hogy P = NP. Ez azt jelenti, hogy ha valaki determinisztikusan polinomiális időben tud megoldani egy NP-teljes problémát, akkor minden NP-beli problémát meg lehet oldani polinomiális időben determinisztikusan is.

9.3.1.1. Egy NP-teljes probléma: a SAT

A SAT (angol: satisfiability, kielégíthetőség szóból) probléma alapvető szerepet játszik a bonyolultságelméletben, ugyanis ez az egyik legismertebb NP-teljes probléma. A feladat maga röviden a következő: adott egy propozicionális logikai formula, döntsük el, hogy kielégíthető-e (vagyis lehet-e a propozicionális változóknak úgy igaz-hamis értéket adni, hogy a formula igaz legyen). A feladatnak többféle speciális megfogalmazása is létezik, és használt mind az elméletben, mind a gyakorlatban. Az első speciális alak, amikor a formula konjunktív normálformában adott. A feladat így is NP-teljes. A következő, még speciálisabb alak, amikor a konjunktív normálforma mellett az is adott, hogy az egyes tagok hány literált tartalmaz(hat)nak. A feladat ilyen megszorítással történő megfogalmazását nevezik n- SAT problémának. Az n- SAT n ≥ 3 esetén NP-teljes, míg a 2-SAT probléma P-beli. A tömör bizonyíték ez esetben egy kielégítő kiértékelés, amely megadja mely Boole-változó értéke legyen igaz és melyek legyenek hamisak. ★

További fontos bonyolultsági osztályok a

PSPACE: determinisztikus Turing-géppel polinomiális szalagigénnyel kiszámolható problémák osztálya;

NPSPACE: nemdeterminisztikus módon polinomiális szalagigénnyel kiszámolható problémák osztálya;

EXP: determinisztikusan exponenciális időben kiszámolható problémák osztálya.

Ismert, hogy a PSPACE és az NPSPACE problémaosztály egybeesik. Itt jegyezzük meg, hogy a környezetfüggő nyelvosztályra a szóprobléma PSPACE-teljes, viszont nemdeterminisztikusan lineáris tárhelyen is megoldható. Mint jeleztük a környezetfüggő nyelveknél a Szóprobléma fejezetben, az viszont nem ismert, hogy determinisztikusan is megoldható-e lineáris tárhelyen.

Az alábbi ábrán a fent említett bonyolultsági osztályok egymáshoz képesti viszonya látható.