Def.: Karp-redukció
L1 Karp - redukálható L2-re, ha minden f polinominális idoben Turing géppel kiszámítható függvény, amelyik w elem L1 <> f(v)eleme L2 L1-ben levo feladatok átalakíthatók L2-beli feladatokká polinomiális idoben.

Tétel: L1, L2, eleme P : L1 Karp- redukálható L2-re (L1<L2)

Ha L1, L2 nyelvek polinominális idoben felismertetheto T turing géppel akkor bármelyik L1 nyelv valamilyen adott függvénnyel átalakítható L2 beli nyelvvé.

Def: L : NP teljes, ha L?NP, L:re Karp-redukálható az összes NP-beli nyelv.
Ha egy nyelv felismertetheto nemdetermisztikus polinominális ideju turing géppel akkor, az adott nyelvvel eloállítható (Karp - redukálható) az összes olyan nyelv amely, bele tartozik a nemdetermisztikus polinominális nyelvosztályba.

Példák:

1.) SAT nyelv: (logikai Boole függvény (és vagy negáció) a kielégítheto Boole függvények nyelve, amelyeknek van plussz 1 nyelve. )
2.) Hamilton körök nyelve: azon gráfok nyelve, amelyek tartalmaznak hamilton kört.
3.) K számmal való színezhetoség
4.) Hátizsák pakolási probléma
Ezek a legnehezebb NP beli feladatok.