7.3. Tár-idő tételek

A tár- és időbonyolultsági osztályok közötti kapcsolatot az alábbi két tétellel fejezhetjük ki.

7.22. Tétel

Legyen  egy monoton függvény. Ekkor
. 

Bizonyítás

Legyen . Ekkor létezik egy időbonyolultságú determinisztikus Turing-gép, amelyikre . Legyen egy bemenő szó, aminek a hossza . Mivel egy Turing-gép minden lépésénél legfeljebb egy új cellába írhat jelet a szalagján, ezért a bemeneten végrehajtott számítás során felhasznált szalag mérete nem lehet nagyobb mint a Turing-gép lépéseinek a száma, vagyis . Ez azt jelenti, hogy , azaz . Ez viszont definíció szerint azt jelenti, hogy , vagyis . ✓

A két osztálytípus közötti fordított összefüggés ettől jóval összetettebb.

7.23. Tétel

Legyen  egy monoton függvény és legyen .
Ekkor létezik  konstans, amelyikre . 

Bizonyítás

Legyen egy tárbonyolultságú determinisztikus Turing-gép, amelyikre .

Tegyük fel, hogy egy olyan hosszúságú szó, amelyiken a Turing-gép megáll.

tulajdonsága miatt ez azt jelenti, hogy a bemeneten történő számítás során, ha , akkor minden esetén.

Ha létezne amelyekre , akkor a Turing-gép sohasem állna meg, hiszen ebben az esetben illetve általánosabban teljesülne, ami azt jelentené, hogy a Turing-gép periodikusan körbe-körbe lépeget ugyanazokon a konfigurációkon.

Ez alapján azt mondhatjuk, hogy a konfigurációk között nincs két egyforma, vagyis értéke nem lehet nagyobb, mint azon konfigurációk száma, amelyhez tartozó szalagtartalom legfeljebb .

Legyen elemszáma . A feletti pontosan $i$ hosszúságú szavak száma , vagyis a legfeljebb $i$ hosszúságú szavak száma .

Ha a elemszáma , akkor az előzőek alapján a feltételeknek megfelelő különböző konfigurációk száma legfeljebb . A formula abból adódik, hogy egy konfigurációban különböző állapot, különböző szalagtartalom és különböző író-olvasó fej pozíció lehet.

Mivel állandó, ezért , ha elegendően nagy. Hasonlóan az is igaz megfelelően nagy -ek esetén. Nagy -ekre az is igaz, hogy .

A három egyenlőtlenséget összeolvasva azt kapjuk, hogy .

Legyen . Az előzőek alapján a számítás hosszára igaz, hogy .

Azt mondhatjuk tehát, hogy minden olyan bemenő szóról amin megáll, legfeljebb időben eldönti, hogy benne van-e -ben vagy sem. Az egyetlen probléma, hogy nem feltétlenül áll meg minden bemeneten. Ezért készítsük el a következő Turing-gépet:

-nek legyen egy második szalagja is, amire minden lépés után elválasztójelekkel elkülönítve felírja az aktuális konfigurációját, és leellenőrzi, hogy ez a konfigurációja szerepelt-e már korábban a szalagon. Ha szerepelt, az azt jelenti, hogy végtelen ciklusba keveredett, vagyis nem fogadja el a bemenetét. Ebben az esetben nemleges válasszal megáll.

számítása természetesen hosszabb mint számítása, mivel minden lépés előtt végig kell mennie a . szalagon. A második szalagon tárolt szó hossza azonban nem lehet nagyobb mint a különböző konfigurációk száma szorozva a konfigurációk maximális méretével, azaz kisebb mint ami megfelelően nagy -ek esetén felülről becsülhető -nel. Így ha időbonyolultsága , akkor . Mivel , ezért megfelelően nagy -ek esetén , valamilyen -re. Legyen ezzel a -vel igaz, hogy elegendően nagy -ekre , azaz ., vagyis . ✓