Chapter 7. Bonyolultságfogalmak

A Turing-gép modell általánossága és egységessége miatt nem csak a kiszámíthatósággal kapcsolatos kérdések megfogalmazására és vizsgálatára alkalmas.

Segítségével az egyes feladatok nehézségére is megfelelően kifejező mértéket definiálhatunk. A hétköznapi életben akkor nevezünk egy feladatot nehéznek, ha a megoldásához olyan műveleteket kell végrehajtanunk, amelyek megértése vagy kivitelezése a megszokottól eltérő, illetve meghaladja (vagy legalábbis súrolja) a képességeink határát. Egy számítógép számára azonban ilyen jellegű gondok nem léteznek. Nem kell megértenie a műveleteket, és amennyiben megfelelően leprogramoztuk, a végrehajtásuk sem okozhat gondot. Algoritmikus szempontból tehát teljesen át kell értelmeznünk egy feladat nehézségét. Ha egy számítógéptől várjuk a feladat megoldását, akkor mondjuk, hogy nehéz a gép számára, ha sokat kell várni a válaszra. Alapvetően ezt a megközelítést fogjuk kiterjeszteni és egzakt módon megfogalmazni a következőkben. Az elemzések és elméleti kutatások legfontosabb területe szintén az algoritmusok és feladatok időszükségletének vizsgálata, bár a pontosabb leírások során a társzükséglet is szerepet kaphat.

7.1. Idő-, tár- és programbonyolultság

Először definiálni fogjuk a determinisztikus és nemdeterminisztikus Turing-gépek idő-, tár- és programbonyolultságát. Ezekkel a fogalmakkal tudjuk kifejezni, hogy egy-egy algoritmusnak (Turing-gépnek) a különböző erőforrásokból milyen mennyiségre van szüksége. A Turing-gép fogalma lehetővé teszi, hogy a mennyiségi egységet nagyon pontosan meghatározzuk.

Mivel az algoritmusainkat általában nem egy feladat megoldására szeretnénk használni, hanem egy egész feladatosztály minden feladatára, ezért az erőforrásszükségletet úgy kell tudnunk kifejezni, hogy a feladatosztály minden elemére kielégítő pontossággal rendelkezzen.

Először a legfontosabb bonyolultságfogalommal, az időbonyolultsággal foglalkozunk.

7.1. Definíció

Legyen  egy determinisztikus Turing-gép és  egy szó. Legyen 
továbbá a  számítása a  bemeneten . 
Tegyük fel, hogy van olyan  amelyre  állapotkomponense 
végállapot. Ekkor azt a legkisebb  értéket amire ez a tulajdonság 
teljesül, a számítás hosszának nevezzük.
Ha nincs ilyen , akkor a számítás hosszát végtelennek tekintjük.
A  Turing-gép által a  bemeneten végrehajtott számítás hossza 
jelekben: , illetve .

A számítás hosszának definíciójával tulajdonképpen az idő fogalmát tudjuk helyettesíteni. Anélkül, hogy tudnánk mit is jelent, definiáltuk az időegységet: egy konfigurációátmenet végrehajtásához szükséges erőforrás. Ezáltal egyben függetlenítjük magunkat attól, hogy a valós idő múlásával fejezzük ki az algoritmusaink, programjaink ilyen jellegű erőforrásigényét. A számítás hosszának segítségével definiálhatjuk a Turing-gépek általános időszükségletét.

7.2. Definíció

Legyen  egy determinisztikus Turing-gép. 
A  Turing-gép időbonyolultsága a  függvény, amelyre: 

         

Amennyiben az egyértelműség nem sérül, az időbonyolultság jelöléséből elhagyhatjuk a Turing-gép megadását. Az így definiált időbonyolultság segítségével azt tudjuk kifejezni, hogy egy adott Turing-gép (algoritmus) egy rögzített korlátnál nem nagyobb méretű feladaton legrosszabb esetben mennyi ideig számol. Emiatt szokás ezt az értéket a legrosszabb esethez tartozó időbonyolultságnak is nevezni.

Hasonló módon értelmezhető az átlagos időbonyolultság, ami a hétköznapi programozás szempontjából lényegesen kifejezőbb mérték, viszont jóval nehezebben kezelhető. Szükséges hozzá többek között a bemenő adatok eloszlásának ismerete, ami a valós esetekben ritkán határozható meg pontosan.

7.3. Megjegyzés

Észrevehetjük, hogy a definíció alapján ha egy Turing-gép 
időbonyolultsága minden  esetén definiált, akkor az minden 
bemeneten megáll, vagyis az általa felismert nyelv rekurzív.

7.4. Megjegyzés

Legyen  egy determinisztikus Turing-gép és  az időbonyolultsága. 
 értéke a leghosszabb számítás hossza a legfeljebb  hosszúságú, 
míg  értéke a leghosszabb számítás hossza a legfeljebb  
hosszúságú bemeneteken. Mivel az utóbbi eset tartalmaz minden bemenetet 
az előbbiből ezért ennek értéke nem lehet kisebb, azaz . 
Ez azt jelenti, hogy  monoton növekvő.

Hasonló módon határozhatjuk meg egy algoritmus (Turing-gép) számítás során jelentkező tárigényét.

7.5. Definíció

Legyen  egy determinisztikus Turing-gép és  egy szó. Legyen továbbá 
a  számítása a  bemeneten . 
Tegyük fel, hogy  és legyen .
Ha létezik ilyen a  értéket a számítás tárigényének nevezzük.
Ha nincs ilyen, akkor a számítás tárigényét végtelennek tekintjük.
A  Turing-gép által a  bemeneten végrehajtott számításhoz szükséges 
tárigényét -vel jelöljük.

Az időbonyolultságnál alkalmazott módszerrel definiálhatjuk a tárbonyolultságot is.

7.6. Definíció

Legyen  egy determinisztikus Turing-gép. A  Turing-gép 
tárbonyolultsága a  függvény, amelyre: 

         

A Turing-gép jelölését természetesen ebben az esetben is elhagyhatjuk, ha nem megy az érthetőség rovására.

Az időbonyolultságéhoz hasonló tulajdonság itt is megfigyelhető.

7.7. Megjegyzés

Legyen  egy determinisztikus Turing-gép és  a tárbonyolultsága.
  értéke a legnagyobb tárigény a legfeljebb  hosszúságú, 
míg  értéke a legnagyobb tárigény a legfeljebb  hosszúságú 
bemeneteken. Mivel az utóbbi eset tartalmaz minden bemenetet az 
előbbiből ezért ennek értéke nem lehet
kisebb, azaz hasonlóan az időbonyolultság esetéhez 
. Ez azt jelenti, hogy  monoton növekvő.

Végül definiáljuk a Turing-gép összetettségét is.

7.8. Definíció

Legyen  egy determinisztikus Turing-gép és  a Turing-gép programja. 
 programbonyolultságának az  értéket nevezzük.

7.9. Megjegyzés

A definíció alapján a programbonyolultság érteke nem függ a bemenet 
hosszától. Az algoritmusok implementációjáról mindez már nem mondható 
el egyértelműen. Amennyiben ugyanis a bemenet értéke egy bizonyos 
korlátot meghalad, más szerkezetű programot kell írnunk. Értelem 
szerűen hosszabb bemenethez hosszabb program tartozik. Más módszereket 
kell ugyanis használni a bemenet beolvasásához, az adatok memóriában 
való tárolásához és előfordulhat, hogy az egyes műveletek is más 
formában jelennek meg.

A determinisztikus Turing-gépekhez hasonlóan nemdeterminisztikus Turing-gépek esetén is definiálhatunk idő- és tárbonyolultságot. Mivel azonban a teljesen általános definíció lényegesen bonyolultabb és kevésbé kifejező lenne, így a megfelelő fogalmakat csak felismerő Turing-gépekre vezetjük be.

7.10. Definíció

Legyen  egy nemdeterminisztikus felismerő Turing-gép és  egy szó. 
Tegyük fel, hogy -nek van olyan számítása a  bemeneten amelyik
elfogadó állapotban megáll. A legrövidebb ilyen lépéseinek számát a 
számítás hosszának nevezzük. 
Ha nincs elfogadó állapotban megálló számítása, akkor a számítás 
hosszát végtelennek tekintjük.
A  által a  bemeneten végrehajtott számítás hosszát a 
determinisztikus Turing-gépekhez hasonló módon -vel jelöljük.

Nemdeterminisztikus Turing-gépek esetén a számítás hosszát csak olyan bemenő szavakra definiáltuk, amelyeket a Turing-gép elfogad. Ennek megfelelően az időbonyolultság fogalmán is módosítani kell egy kicsit.

7.11. Definíció

Legyen  egy nemdeterminisztikus Turing-gép. 
A  Turing-gép időbonyolultsága a  függvény, amelyre: 
.

A nemdeterminisztikus Turing-gépek tárbonyolultságát a következőképen definiálhatjuk.

7.12. Definíció

Legyen  egy nemdeterminisztikus felismerő Turing-gép és  egy szó. 
Tegyük fel, hogy -nek van olyan számítása a  bemeneten amelyik
elfogadó állapotban megáll. 
Legyen  egy elfogadó állapotban megálló lehetséges számítása a
 bemeneten . Tegyük fel, hogy  
és legyen .
Az  elfogadó számításhoz tartozó tárigény: 
.
A lehetséges elfogadó számításokhoz tartozó tárigények közül a 
legkisebbet a Turing-gép  bementhet tartozó tárigényének nevezzük. 
Ha nincs elfogadó állapotban megálló számítása, akkor a számítás 
tárigényét végtelennek tekintjük.
A  által a  bemeneten végrehajtott számítás tárigényét a 
determinisztikus Turing-gépekhez hasonló módon -vel jelöljük.

Hasonlóan az időbonyolultsághoz, a nemdeterminisztikus Turing-gépek esetén a számítás tárigényét csak olyan bemenő szavakra definiáltuk, amelyeket a Turing-gép elfogad. Ennek megfelelően az tárbonyolultság fogalmán is módosítani kell egy kicsit.

7.13. Definíció

Legyen  egy nemdeterminisztikus Turing-gép. 
A  Turing-gép tárbonyolultsága a  függvény, amelyre: 

         

A következő tétel a rekurzív nyelvek alaposabb megismeréséhez nyújt segítséget. Azt láthatjuk be általa, hogy ha egy nyelv rekurzív felsorolható és időbonyolultsága nem túl nagy, akkor a nyelv egyben rekurzív is. Ez azt jelenti, hogy ha egy nyelv nem rekurzív, akkor (ha van egyáltalán) az őt felismerő Turing-gép időbonyolultsága kiszámolhatatlanul nagy. A kiszámolhatatlanul nagy az tényleg valami nagyon gyorsan növő függvényt jelent, hiszen még az Ackermann-függvény is kiszámolható.

7.14. Tétel

Legyen  egy nyelv. Tegyük fel, hogy létezik egy  Turing-géppel 
kiszámolható függvény és egy  determinisztikus Turing-gép, 
amelyikre . 
Amennyiben  az  elemein legfeljebb  lépésben megáll, akkor .

Bizonyítás

Legyen az a Turing-gép, amelyik kiszámolja -t, azaz és legyen a korábbiakban megismert elven -ből készített korlátozott futásidejű Turing-gép. Ezek segítségével készítsük el a következő működésű Turing-gépet:

1. A bemenet alapján az új Turing-gép . szalagjára írjunk darab -t.

2. A bemeneten indítsuk el a Turing-gépet. Ha a futás során a rész áll meg előbb, akkor annak döntése lesz a tényleges végállapot, ha a korlátozó rész áll meg előbb akkor nemleges választ adunk.

Világos, hogy az új Turing-gép minden bemeneten megáll, és pontosan azokat a szavakat fogadja el, amelyeket amúgy is elfogadott, hiszen ha elfogadja, akkor azt kevesebb mint lépésben teszi. Definíció szerint ez azt jelenti, hogy . ✓