1.4. Bonyolultságelméleti alapfogalmak

Ebben a fejezetben néhány fontos bonyolultsági osztályt említünk meg. Egy számítás idő- és tárigényét az input szó hosszának függvényében szokás megadni. 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) vizsgáljuk.

Legyen egy determinisztikus Turing-gép, a (vagyis és hossza ) input szón a számítás időigényének a függvényt nevezzük, mely a következő alakú:

, ha a inputon lépés utá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 vonatkozik.

Azt mondjuk, hogy egy determinisztikus Turing-gép időigénye (legfeljebb) , ha futási ideje egyetlen legfeljebb hosszú bemenetre sem több -nél. Ha egy időigényű Turing-gép elfogad egy nyelvet, akkor azt mondjuk, hogy . egy bonyolultsági osztály, ami tartalmazza azokat a nyelveket, amelyek időben eldönthetőek.

Formálisan tehát a Turing-gép időbonyolultsága (maximális időbonyolultsága) : Az időbonyolultság fogalma jól rokonítható a számítógépeinken futó algoritmusaink futási idejével.

Azon nyelvek (problémák) halmazát, amelyekhez van olyan determinisztikus Turing-gép, ami ezek szavait valamilyen polinomfüggvénnyel megadható időben eldönti (kiszámítja), P bonyolultsági osztálynak nevezzük.

A P osztály problémáiról úgy gondoljuk, hogy őket hatékonyan meg tudjuk oldani hagyományos számítógépeken.

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 nemdeterminisztikus verzióját is szokás használni, ahogy a definíciót már mutattuk. Itt a kiszámíthatóságot úgy definiáljuk, 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 determinisztikus 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, mint szisztematikusan keresve. A következő részben egy kicsit 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.

Legyen tehát most egy nemdeterminisztikus Turing-gép. Azt mondjuk, hogy időben eldönti/felismeri az nyelvet, ha bármely szóra a megfelelő kezdőkonfigurációból indulva van olyan számítás, amely elfogadja -t legfeljebb lépés után, ahol a hossza. Azon nyelvek halmazát, amelyekhez van olyan nemdeterminisztikus Turing-gép, ami ezek szavait valamilyen polinomfüggvénnyel megadható időben eldönti (kiszámítja), NP bonyolultsági osztálynak nevezzük.

A számítástudomány egyik legfontosabb eddig sem nem bizonyított, sem nem cáfolt 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 van hozzá egy „tanúnyelv”, amiben az nyelv minden szavára létezik egy „tömör bizonyíték” (ami polinomiális időben ellenőrizhető) arra, hogy benne van az nyelvben. Azokra a szavakra, amelyek nem elemei az nyelvnek nincs ilyen bizonyíték.

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 problémát NP-teljesnek nevezünk, ha abból, hogy P, az következik, hogy P = NP. Ez az 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.

További fontos bonyolultsági osztályok a PSPACE, vagyis a determinisztikus Turing-géppel polinomiális szalagigénnyel kiszámolható problémák osztálya. Érdekes módon ez a problémaosztály megegyezik a nemdeterminisztikus Turing-géppel polinomiális szalagigénnyel kiszámolható problémák osztályával.

Az EXP problémaosztály pedig a determinisztikus Turing-gépekkel exponenciális időben kiszámolható problémák osztálya.

Az 1.3. ábrán a fent említett bonyolultsági osztályok egymáshoz képesti viszonya látható. Azt tudjuk, hogy a P-t szigorúan tartalmazza az EXP (vagyis P EXP), de hogy a P és NP, az NP és PSPACE, vagy a PSPACE és EXP viszonyok közül melyik tartalmazás a szigorú, és hol van egyenlőség az nem ismert. Az ezzel foglalkozó tudósok nagy része úgy gondolja, hogy ezek a bonyolultsági osztályok szigorú hierarchiát alkotnak, vagyis nincs köztük megegyező.

1.3. ábra - A fontosabb bonyolultsági osztályok hierarchiája.

A fontosabb bonyolultsági osztályok hierarchiája.

A P-NP probléma kb. úgy is felfogható, mint annak a kérdése, hogy vannak-e olyan problémák, amelyek esetén a megoldás ellenőrzése (sokkal) egyszerűbb, mint a megoldás megtalálása (determinisztikus módon). A következő alfejezetekben két széles körben ismert NP-teljes problémát ismertetünk.

1.4.1. A SAT probléma megfogalmazása

A SAT 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 (vagy más néven ítélet-, vagy Boole-) logikai formula, döntsük el, hogy kielégíthető-e, vagyis lehet-e a propozicionális változóknak (ítéletváltozók, Boole-változók) értéket adni úgy, 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ál formában adott. Az ítéletváltozókat, illetve negáltjaikat (pozitív, illetve negatív) literáloknak hívjuk. Literálok diszjunkcióját elemi diszjunkciónak (vagy klóznak) nevezzük. Elemi diszjunkciók konjunkciója adja a konjunktív normálformájú formulát. Közismert tény, hogy minden propozicionális logikai formulához van vele ekvivalens konjunktív normálformájú formula. A feladat maga így is NP-teljes. A következő, még speciálisabb alak, amikor a konjunktív normál forma mellett az is adott, hogy az egyes elemi diszjunkciók hány literált tartalmaz(hat)nak. A feladat ilyen megszorítással történő megfogalmazását nevezik -SAT problémának. Az -SAT 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.

Itt említjük meg, hogy diszjunktív normál formájú formulák esetén a SAT probléma megoldása triviális. Literálok konjunkcióját elemi konjunkciónak hívjuk. Elemi konjunkciók diszjunkciója adja a diszjunktív normál formát. Minden ítéletlogikai formulával van ekvivalens diszjunktív normálformájú formula is. A kiértékelő algoritmus egyszerű: tekintsük az első elemi konjunkciót: legyenek a benne szereplő pozitív literálok igazak, a negatív literálok változói pedig hamisak. Mivel a formula többi része diszjunkcióval kapcsolódik, nem érdekes az igazságértéke, a diszjunkció egyik tagjának igazsága az egész formulát igazzá teszi. Egyetlen egy esetben nem sikeres az értékadás: ha az elemi konjunkcióban van olyan ítéletváltozó, ami pozitív és negatív literálként is szerepel. Ekkor az adott elemi konjunkció nem kielégíthető, az algoritmusnak a következőt is ellenőriznie kell. Ha találunk kielégíthető elemi konjunkciót (az előbbi módon igazságértékeket rendelhetünk a Boole változókhoz), a formula kielégíthető. Ha egyik elemi konjunkció sem kielégíthető, akkor a formula sem. Ez tehát egy lineáris algoritmus, vagyis a leghatékonyabb algoritmusok egyike. Hol van akkor a bökkenő, hogy lehet mégis nehéz a SAT? Hiszen köztudottan konjunktív normálformájú formulát egyszerűen átkonvertálhatunk diszjunktív normálformájúvá a disztributív azonosságok segítségével. Gondoljunk csak bele, hogyan változik a formula hossza ezzel a transzformációval... A diszjunktív normálformájú formulákra annak eldöntése nehéz, hogy a formula logikai törvény-e (vagyis, hogy minden lehetséges kiértékelés esetén igaz lesz-e). Ez a kérdés a konjunktív normálformájú formulák esetén oldható meg egyszerűen.

A SAT probléma jelentőségére mutat rá, hogy évente rendeznek rangos konferenciát International Conference on Theory and Applications of Satisfiability Testing címmel, ahol kutatók mutatják új eredményeiket, újabb és újabb programjaikat amikkel egyre hosszabb, és egyre több ítéletváltozót tartalmazó formulákra oldják meg a problémát.

1.4.2. A Hamilton-út probléma megfogalmazása

A Hamilton-út probléma a gráfelmélet egyik legismertebb NP-teljes problémája. Adott egy csúcsú (irányított) gráf. A feladat, hogy megadjunk egy olyan élsorozatot, utat (vagy azt, hogy van-e ilyen a gráfban), amely a gráf minden csúcsát pontosan egyszer tartalmazza és benne (az első kivételével) minden él onnan indul, ahova az előző él érkezett. Az ilyen típusú utat hívjuk Hamilton-útnak. Semmilyen egyszerű feltétel nem ismert ilyen út létezésének eldöntésére (szemben pl. az Euler-út problémájával, ahol a gráf minden élének pontosan egyszer kell az útban szerepelnie).

Ez esetben a polinomiálisan ellenőrizhető bizonyíték magának egy Hamilton-útnak a megadása.

Az új számítási paradigmák egy részének éppen az adta a motivációs alapot, hogy nemhagyományos módon ugyan, de gyors, hatékony választ ígérnek olyan problémákra és feladatokra, amelyekre a hagyományos számítógépek nem képesek.