7.2. Bonyolultsági osztályok

A Turing-gépek bonyolultságfogalmai alapján feladatok nehézségét is definiálhatjuk. Ezek a definíciók lényegében azt fogalmazzák meg, hogy egy feladat olyan nehéz, mint az őt megoldó megfelelő szempontból vizsgált legjobb algoritmus (Turing-gép) bonyolultsága.

7.15. Definíció

Legyen   egy monoton növekvő függvény. 
Ekkor a

halmazt az  időben determinisztikus Turing-géppel megoldható 
feladatok osztályának nevezzük.

7.16. Definíció

Legyen   egy monoton növekvő függvény. 
Ekkor a 

halmazt az  tárral determinisztikus Turing-géppel megoldható 
feladatok osztályának nevezzük.

7.17. Definíció

Legyen   egy monoton növekvő függvény. 
Ekkor az

halmazt az  időben determinisztikus Turing-géppel megoldható 
feladatok osztályának nevezzük.

7.18. Definíció

Legyen   egy monoton növekvő függvény. 
Ekkor az 
 
halmazt az  tárral determinisztikus Turing-géppel megoldható 
feladatok osztályának nevezzük.

Az egyes időbonyolultsági osztályok között a következő egyszerű összefüggés állapítható meg.

7.19. Tétel

Legyen  és  két monoton függvény, amelyekre .
Ekkor .

Bizonyítás

Mivel , ezért . Ez azt jelenti, hogy ha egy függvényre akkor is teljesül. Az fentebbi definíció szerint, ha akkor létezik időbonyolultságú determinisztikus Turing-gép, amelyikre . Mivel ekkor is teljesül, ezért , azaz . ✓

Hasonló eredmény a többi bonyolultsági osztályra is bizonyítható.

7.20. Tétel

Legyen  és  két monoton függvény, amelyekre .
Ekkor 
1. ;
2. ;
3. .

Bizonyítás

A bizonyítás teljesen hasonló az előző tételéhez. ✓A determinisztikus és nemdeterminisztikus bonyolultsági osztályok között is megállapítható egy egyszerű összefüggés.✓

7.21. Tétel

Legyen  egy monoton függvény.
Ekkor 
1. ;
2. .

Bizonyítás

Ha , akkor definíció szerint -hez létezik időbonyolultságú determinisztikus Turing-gép, amelyre . Mivel minden determinisztikus Turing-gép tekinthető nemdeterminisztikusnak, ezért ugyanezzel a Turing-géppel a tulajdonság is teljesül, vagyis .

Hasonlóan bizonyítható a állítás is. ✓

A nyelvosztályok közül kiemelhetünk néhányat, amelyek az algoritmikus vizsgálatok során kiemelt szerepet játszik. Ezek a következők:

1. : a lehető legegyszerűbb feladatok. Ha ugyanis valamilyen 
feladatnak  időbonyolultsága van úgy, hogy  (azaz  
határozottan lassabban nő mint ), akkor a feladatot megoldó Turing-gép 
nem olvashatja végig a teljes bemenetet.
Néhány ide tartozó feladat: összeadás, keresés, egy szó tükrözése, 
negálás, paritásellenőrzés és általában a reguláris nyelvek felismerése.

2. : az előző osztályhoz képest egy kicsit nehezebb feladatok.
Ide tartozik pl. szorzás, osztás, mátrix-szorzás, polinom szorzás, 
rendezés, két szó leghosszabb közös részsorozatának keresése.

3.  azaz a determinisztikus 
Turing-géppel polinomiális időben megoldható feladatok osztálya.
Ide tartoznak a viszonylag egyszerűen megoldható feladatok:
pl. legnagyobb közös osztó megkeresése, gráfban legrövidebb utak
keresése, gráfban minimális súlyú feszítőfa keresése, legnagyobb
áteresztőképesség számítása.

4.  azaz a determinisztikus
Turing-géppel exponenciális időben megoldható feladatok osztálya.
Lényegében a gyakorlatban előforduló feladatok nagy többsége ide
tartozik. Ez csalóka megfigyelés, ugyanis megszámlálhatóan végtelen
sok megoldható feladat nem tartozik ebbe az osztályba, viszont ilyenek
a gyakorlatban nem nagyon kerülnek a látókörünkbe.

5. : a lineáris tárral nemdeterminisztikus Turing-géppel
megoldható feladatok. Pl. a környezetfüggő nyelvek felismerése.

6. 

7. : a nemdeterminisztikus Turing-géppel lineáris időben
megoldható feladatok. Meglepően sok feladat tartozik ide.

8.  a nemdeterminisztikus 
Turing-géppel polinomiális időben megoldható feladatok.
Bonyolultságelméleti szempontból az egyik legérdekesebb nyelvosztály.