8.2.  NP-teljesség

Az előzőekben megvizsgáltuk hogyan tudjuk ellenőrizni egy nyelv -be tartozását. Még mindig nem tisztáztuk azonban, hogy szükséges-s ez egyáltalán. Azt tudjuk ugyan, hogy de nem beszéltünk arról, hogy a tartalmazás valódi-e, vagy egyenlőség áll fenn. Bár elvileg semmi nem zárja ki a bizonyítás lehetőségét, mind a mai napig nem ismert sem a bizonyítása, sem a cáfolata annak, hogy .

Az állítást cáfolni úgy lehetne, hogy keresünk egy -beli nyelvet, amiről belátjuk, hogy determinisztikus Turing-géppel nem lehet polinomiális időben felismerni.

A cáfolatára és igazolására is komoly erőfeszítéseket tettek. Ez utóbbi érdekében vezették be az -tejesség fogalmát. Ha röviden akarjuk meghatározni, az -teles nyelvek az különleges tulajdonságú, legnehezebb feladatinak tekinthetők. Ha akár csak egyről is sikerülne belátni, hogy -be tartozik, akkor az összes -beli nyelvere igaz lenne.

Az első szükséges fogalom a következő.

8.3. Definíció (Karp-redukció)

Legyen  két nyelv. Azt mondjuk, hogy  Karp-redukálható -re 
(jelekben:  ), ha létezik egy  polinomiális időbonyolultságú 
determinisztikus Turing-gép, amelyikkel  esetén  akkor és 
csak akkor, ha .

8.4. Megjegyzés

A Karp-redukálhatóság megközelítőleg annyit jelent, hogy ha van 
egy feladatunk, azt könnyen át tudjuk fogalmazni egy másik 
feladattá, illetve ha ezt a másikat - egyszerűen - meg tudjuk 
oldani, akkor az eredeti feladatot is - egyszerűen - meg 
tudjuk oldani. Erre utal a jelölés is: a könnyebb feladat felől 
a nehezebb irányába nyílik a jel.

A Karp-redukciót arra tudjuk használni, hogy a nyelveket (feladatokat) nehézség szerint összehasonlítsuk. Ehhez belátjuk a Karp-redukálhatóság, mint reláció néhány tulajdonságát.

8.5. Tétel

Legyen  három nyelv. Ekkor
1.  (reflexivitás),
2. ha  és  akkor  (tranzitivitás). 

Bizonyítás

1. A Karp-redukció definíciójában a leképező Turing-gép legyen egy olyan Turing-gép, ami amikor elindul, egyből megáll, anélkül, hogy a szalagjának tartalmát megváltoztatta volna. Ez a Turing-gép az identikus leképezést valósítja meg, azaz , minden bemeneten. A definíció alapján ekkor pontosan a bizonyítandó állítást kapjuk.

2. Legyen és két olyan Turing-gép, amelyikkel a Karp-redukció definíciójában levő átalakítást végezzük az és relációknak megfelelő sorrendben, és legyen a két Turing-gép időbonyolultsága és , az indexeknek megfelelően, melyek fokszáma és . Legyen . Erre a Turing-gépre igaz az, hogy ha akkor . Ez alapján, a definíciót felhasználva .

Ha egy hossza , akkor legfeljebb időben kiszámolja -et. hossza legfeljebb annyi, mint amennyi ideig számol a Turing-gép, hiszen egy lépésben csak egy új jelet írhat a szalagra (egészen pontosan csak minden második lépésben írhat egy jelet), azaz . A Turing-gép számításának hossza -en legfeljebb . Legyen a időbonyolultsága. Az előzőek alapján egy tetszőleges legfeljebb hosszúságú bemeneten a Turing-gép számításának hossza legfeljebb , azaz . Beláttuk tehát, hogy polinomiális időbonyolultságú Turing-gép és teljesülnek rá a Karp-redukció definíciójánál előírt feltételek, vagyis . ✓

A Karp-redukálhatóság szűkítésével egy ekvivalenciarelációt definiálhatunk.

8.6. Definíció

Legyen  és  két nyelv. Azt mondjuk, hogy  és  Karp-ekviavalensek  
(jelekben ), ha  és .

8.7. Tétel

A Karp-ekvaivalencia tényleg ekvivalenciareláció, 
azaz  nyelvek esetén
1. ;
2. ha , akkor ;
3. ha  és , akkor .

Bizonyítás

Az 1. és 3. eset a Karp-redukálahatóság 1. és 2. tulajdonságainak egyszerű következménye, a 2. eset pedig a definíció alapján könnyen látható, hiszen a két reláció és a nyelvek sorrendjétől függetlenül igazak. ✓

8.8. Megjegyzés

Két nyelv (feladat) akkor Karp-ekvivalens, ha polinomiális 
időben egymásba alakíthatók, azaz a nehézségük polinomiális 
átalakítástól eltekintve azonos.

A Karp-redukálhatóság értelmezése alapján nem meglepő a következő tétel.

8.9. Tétel

Legyen  és  két nyelv, amelyikre . Ekkor
1. ha , akkor  is igaz;
2. ha , akkor  is igaz. 

Bizonyítás

Legyen egy polinomiális időbonyolultságú Turing-gép, amelyikkel a Karp-redukálhatóság igazolható.

1.

Mivel , ezért létezik egy polinomiális időbonyolultságú Turing-gép, amelyikre . Legyen . A Karp-redukció definíciója alapján , azaz .

Legyen és , valamint egy hosszúságú szó és . A bemeneten legfeljebb ideig számol, és . A bemeneten legfeljebb ideig számol, amiből az előző tételekhez hasonlóan Turing-gép időbonyolultságára azt kapjuk, hogy , azaz polinomiális időbonyolultságú. Ezzel az állítást igazoltuk.

2.

Hasonlóan az előző esethez, mivel , ezért létezik egy polinomiális időbonyolultságú nemdeterminisztikus Turing-gép, amelyikre . Legyen . A Karp-redukció definíciója alapján , azaz .

Legyen és , valamint egy hosszúságú szó és . A bemeneten legfeljebb ideig számol, és . Mivel az előzőek miatt ezért legfeljebb időben elfogadja, amiből az előző tételekhez hasonlóan nemdeterminisztikus Turing-gép időbonyolultságára azt kapjuk, hogy , azaz polinomiális időbonyolultságú. Ezzel az állítást igazoltuk. ✓

Az alábbi tétel meghatározza a Karp-ekvivalencia alapján legkönnyebb feladatok osztályát.

8.10. Tétel

Legyen  két nem triviális nyelv (azaz nem üresek és a 
komplementerük sem az). Ekkor .

Bizonyítás

Elegendő azt belátni, hogy , ekkor ugyanis a szimmetria miatt is teljesül.

Mivel nem triviális nyelv, ezért léteznek és szavak. Továbbá, mivel , ezért létezik egy polinomiális időbonyolultságú determinisztikus Turing-gép, amelyikre .

Legyen és olyan Turing-gépek, amelyek letörlik a szalagjukat és -t illetve -t írnak rá.

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

Ekkor egy tetszőleges szó esetén . Mivel polinomiális és pedig konstans időbonyolultságú, ezért is polinomiális időbonyolultságú Turing-gép. Ez viszont definíció szerint pontosan a bizonyítandó állítás. ✓

8.11. Megjegyzés

Ha bármely két nem triviális -beli nyelv Karp-ekvivalens 
lenne, akkor a  egyenlőség igaz lenne. Legyen ugyanis 
az egyik nyelv egy rögzített , a másik pedig egy 
tetszőleges . Mivel , ez azt jelentené, hogy .

Mivel a állítás igazságát nem ismerjük, ezért nem tudjuk, hogy Karp-ekvivalens-e bármely két -beli nyelv. Definiálható viszont egy ehhez szorosan kötődő tulajdonság.

8.12. Definíció

1. Egy  nyelvet -nehéznek nevezünk, ha minden -beli 
nyelv Karp-redukálható rá.
2. Egy  nyelvet -teljesnek nevezünk, ha -beli és -nehéz.

Egy nyelv -teljessége azt jelenti, hogy az -beli nyelvek (feladatok) közül a legnehezebb.

8.13. Megjegyzés

Ha egy -teljes nyelvről sikerülne belátni, hogy -beli, 
akkor a  igaz lenne.

Egyáltalán nem nyilvánvaló, hogy létezik -teljes nyelv. Ha viszont sikerül egyet találni, akkor egy újabb nyelv -teljességének igazolásához már csak azt kell ellenőrizni, hogy -beli legyen és Karp-redukálható legyen rá a másik -teljes nyelv. (A tranzitív tulajdonság miatt ugyanis ekkor minden -beli nyelv redukálható rá.) Ezen az elven már sok -beli nyelvről sikerült igazolni az -teljességet. Néhányat közülük a következő listában adunk meg.

-teljes nyelvek:

1. - nyelv: a kielégíthető konjunktív normálformák nyelve.

2. A Hamilton-körrel rendelkező gráfok nyelve.

3. A színnel színezhető gráfok nyelve.

4. -klikk probléma (k-elemű teljes részgráf létezése)

5. -csúcsú lefedés gráfokban