15.3. Bonyolultságelméleti alapfogalmak

Amikor egy probléma algoritmikus jellegű megoldását keressük, általában nem egy teljesen meghatározott feladatról van szó, hanem az tartalmaz valamilyen paramétert, ami által a probléma általában nem egy konkrét feladat, hanem egy egész feladatosztály.

Az algoritmus fogalmát a következőképpen adhatjuk meg:

Az egyik legelterjedtebben használt algoritmusmodell a Turing-gép. Itt a lépések a Turing-gép átmenetfüggvénye alapján értendőek. Érdekes módon ugyanazok a problémák oldhatóak meg más algoritmus leírásra használt módszerekkel (lambda-kalkulus, parciálisan rekurzív függvények, Markov normál algoritmusa, RAM-gép, Post kanonikus rendszere stb.).

Ebben a fejezetben néhány fontos bonyolultsági osztályt említünk meg, amiket a Turing-géppel történő algoritmus megadás és végrehajtás alapján szokás definiálni. 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ő: lépésszám, tár: szalag) vizsgáljuk.

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

tM(w) = max{n, k}, ha M a w inputon k 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 M Turing-gép időigénye (legfeljebb) f(n), ha M futási ideje egyetlen legfeljebb n hosszú bemenetre 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 LTIME(f(n)). TIME(f(n)) egy bonyolultsági osztály, ami tartalmazza azokat a nyelveket, amelyek f(n) időben eldönthetőek.

Formálisan tehát az M Turing-gép időbonyolultsága (maximális időbonyolultsága): tM(n) = max{tM(w), ahol ∣w∣ ≤ n}. 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).

Nézzük most a nemdeterminisztikus Turing-gépeket. 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'' (,,megérzéssel'') hamarabb találhatunk megoldást, mint szisztematikusan keresve. Lássuk, 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 M egy nemdeterminisztikus Turing-gép. Azt mondjuk, hogy M f(n) időben eldönti/felismeri az L nyelvet, ha bármely wL szóra, a megfelelő kezdőkonfigurációból indulva, van olyan számítás, amely elfogadja w-t legfeljebb f(n) lépés után, ahol n a w 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 (N a nemdeterminisztikus, P pedig a polinomiális szavakból).

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 L nyelvre (problémára) igaz, hogy van hozzá egy „tanúnyelv'', amiben az L nyelv minden w szavára létezik egy tömör (polinomiális időben ellenőrizhető) bizonyíték arra, hogy w benne van az L nyelvben. Azokra a szavakra, amelyek nem elemei az L nyelvnek nincs ilyen bizonyíték.

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).

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 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. A legismertebb NP-teljes problémák a SAT (Boole logikai formulák kielégíthetőségének eldöntése) és a Hamilton-út probléma, vagyis hogy adott gráfban van-e olyan út (séta)/kör, amely minden csúcspontot érint pontosan egyszer (kör esetén az első és utolsó csúcs kivételével, amik megegyeznek, így pontosan kétszer kell hogy szerepeljenek), amik a 3.2.1. és 3.1.1. alfejezetekben találhatóak meg részletesebben leírva.

További fontos bonyolultsági osztályok a LINSPACE és a PSPACE, vagyis a determinisztikus Turing-géppel lineáris, illetve polinomiális szalagigénnyel kiszámolható problémák osztálya. Érdekes módon a PSPACE problémaosztály megegyezik a nemdeterminisztikus Turing-géppel polinomiális szalagigénnyel kiszámolható problémák osztályával, vagyis azt mondhatjuk, hogy PSPACE = NPSPACE. Nagyon érdekes, hogy a korábban ismertetett nemdeterminisztikus lineárisan korlátozott automata, ami az NLINSPACE feladatosztály feladatainak megoldására képes, már tartalmaz PSPACE-teljes feladatot. Ennek ellenére a hierarchia nem omlik össze, minden k kitevőre van olyan probléma/nyelv, amely k-adfokú polinommal adott tárhelyen nem megoldható, de egy (k + 1)-fokú polinommal adott tárhelyen már megoldható (és mindez a determinisztikus és a nemdeterminisztikus esetre is érvényes külön-külön). Savitch tétele értelmében az NLINSPACE feladatosztály determinisztikusan négyzetes szalagigényű Turing-géppel (vagyis olyan determinisztikus Turing-géppel, ami az input hosszának négyzetes függvényével korlátozott szalagterületen dolgozhat) jellemezhető. Az, hogy vajon lineáris szalagméret elegendő-e minden NLINSPACE-beli probléma determinisztikus Turing-géppel való megoldásához, a bonyolultságelmélet egy fontos és nehéznek tűnő máig megoldatlan problémája: LINSPACE ≡? NLINSPACE.

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

15.1. ábra - A fontosabb bonyolultsági osztályok hierarchiája (nem tudjuk, hogy mely tartalmazások valódiak).

A fontosabb bonyolultsági osztályok hierarchiája (nem tudjuk, hogy mely tartalmazások valódiak).

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