Chapter 8. Az NP nyelvosztály

Az nyelvosztályok vizsgálata érdekes megfigyelésekre vezet. Ahogy az előző fejezetben láthattuk, hogy . Felvetődik azonban a kérdés, hogy vajon az összefüggés valódi részhalmazt jelöl-e, vagy vannak olyan esetek, ahol a két nyelvosztály között egyenlőség áll fenn. A gyakorlati alkalmazások szempontjából az egyik legfontosabb a nyelvosztály, hiszen ide tartoznak a viszonylag elfogadható időben megoldható feladatok. Ennek kapcsolata -vel egy igen sokat kutatott területe az algoritmuselméletnek.

A következőkben először is azzal foglalkozunk, hogy hogyan értelmezhetjük az -be tartozó feladatokat.

8.1. A Tanú-tétel

Elsőre nyilvánvalónak tűnik, hogy vannak feladatok, amelyek esetén a megoldás (vagy a megoldásra utaló valamilyen információ) ismeretében könnyebben meg tudjuk oldani a kérdéses feladatot - az előző fejezet alapján azt mondhatjuk, hogy algoritmikus szempontból a könnyebb megoldás a gyorsabbat jelenti. Óvatosan kell azonban a megoldás jelentésével bánni. Egy feladatot ugyanis csak akkor tekinthetünk megoldottnak, ha nem egyszerűen ismerjük a megoldást, hanem biztosak lehetünk benne, hogy valóban az. Ilyen megközelítésben már egyáltalán nem nyilvánvaló, hogy mely feladatok megoldását tudjuk bizonyos ismeretek birtokában gyorsabban meghatározni .

Hiába mondja meg például valaki, hogy , ahhoz, hogy biztosak legyünk az eredmény helyességében, lényegében újra ki kell számolnunk a szorzatot. Ha viszont szeretnénk meghatározni prímtényezős felbontását, és valaki elárulja, hogy , akkor a keresgélés helyett nekünk már csak egyszerűen egy szorzást kell elvégezni, illetve ellenőrizni, hogy a tényezők valóban prímszámok.

Az -be tartozó nyelvek hasonló megközelítéssel írhatók körül. A következő tételben be fogjuk látni, hogy lényegében akkor tartozik egy feladat -be, ha megadható a megoldására vonatkozó nem túl sok információ, ami alapján viszonylag gyorsan meg tudjuk határozni a megoldást.

8.1. Tétel (Tanú-tétel)

Legyen  egy nyelv. Ekkor a következő állítások ekvivalensek:
1. .
2. Létezik egy  
            -beli nyelv és egy  polinom, amelyekre 
 akkor és csak akkor, ha  úgy, hogy  és .

Bizonyítás

A tétel két állítást foglal magába: az első szerint 1. implikálja 2-t, a második szerint pedig 2. implikálja 1-t. Ennek megfelelően a bizonyítást is két részre bontjuk.

A. 1. ⇒ 2.

Mivel , ezért létezik egy polinomiális időbonyolultságú nemdeterminisztikus Turing-gép, amelyikre .

Legyen időbonyolultsága . Ez azt jelenti, hogy minden esetén -nek létezik egy lehetséges számítása -n, ahol elfogadó állapotot tartalmaz, és .

A nemdeterminisztikus Turing-gépek definíciója szerint minden és esetén . Minden esetén rögzítsük elemeinek a sorrendjét, azaz tegyük fel, hogy .

Ez alapján, ha adott egy számítása, azt leírhatjuk egy sorozattal, ahol annak az utasításnak (állapotátmenetnek) az indexe, amelyiket a lépésben ténylegesen végrehajtottunk. Világos, hogy minden esetén. Ez azt jelenti, hogy ábrázolható -fölötti szóként legfeljebb hosszon, ahol . Itt . (Ha pontosabbak akarunk lenni, -ból el kell hagynunk néhány vezérlő jelet az -k ábrázolásához, így értéke helyett egy kisebbel kell dolgoznunk, de ez nem változtat a tényen, hogy létezik egy megfelelő .) A konstans értéke csak -től függ.

Egy szóhoz alapján rendeljük hozzá azt a szót, amit a legrövidebb elfogadó számításához tartozó indexsorozat leírásával kapunk, azaz legyen . Ekkor . Legyen a tételben szereplő polinom .

Legyen továbbá .

A tétel első felének igazolásához már csak annyi kell belátni, hogy .

Legyen egy determinisztikus Turing-gép, amit alapján definiálunk.

Eltekintve a teljesen pontos leírástól, a állapothalmazát egyszerűen -ként, míg átmenetfüggvényét -ként definiáljuk, ahol a halmaz -dik eleme.

A Turing-gép lényegében szimulálja a működését. Az első szalagján a szalagtartalma, a másodikon a segédszó található. Számítása során a szót egyszer olvassa végig, de szakaszosan. Minden szimulált lépés előtt megnézi következő komponensét, és ennek értékétől függően hajtja végre az első szalagról beolvasott jelre a által meghatározott konfigurációátmenetet.

A Turing-gép így pontosan a konfigurációsorozatnak megfelelő számítást hajtja végre, vagyis pontosan azokat a szavakat fogadja el, amelyek -be tartoznak.

Időbonyolultsága lineáris, hiszen a bemenő szót (pontosabban annak jelentős részét, -t) csak egyszer olvassa el.

Ezzel a tétel első felét beláttuk.

B. 2. ⇒ 1.

Legyen az -t felismerő polinomiális időbonyolultságú determinisztikus Turing-gép, és legyen az a nemdeterminisztikus Turing-gép, amelyik a bemenő szava mögé ír egy jelet és az összes lehetséges -beli szót.

Definiáljuk a következő nemdeterminisztikus Turing-gépet:

Ez lényegében annyit csinál, hogy a bemenő szó mögé írja az össze lehetséges szót, és kipróbálja, hogy benne van-e az így kapott szó -ben. Mivel a tétel állításában szereplő $v$ hossza , a időbonyolultsága a következőképpen határozható meg:

Legyen . Amíg a komponens számol, addig lépést tesz meg. A második szakaszban, végrehajtása során legfeljebb ideig számol. Legyen fokszáma , fokszáma pedig . Ekkor szintén polinom, aminek fokszáma , ezért a nemdeterminisztikus Turing-gép időbonyolultsága , vagyis . ✓

8.2. Megjegyzés

1. A tételben szereplő  szót a  egy tanújának nevezzük.
2. Az előbbi tétel alapján azt mondhatjuk, hogy a tanú segítségével 
ellenőrizhetjük, hogy egy szó beletartozik-e az adott nyelvbe. 
Emiatt a tulajdonsága miatt az -be tartozó nyelveket polinomiális 
időben ellenőrizhető nyelveknek is szokták nevezni.