Třída NP-úplných problémů
NP-úplné problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase (tedy že NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Tento vztah se řadí mezi jeden z problému tisíciletí a za jeho vyřešení se nabízí velká odměna ;)
Definice NP-úplných problémů 
Skupina nejtěžších NPTIME problémů. Problém je NP-úplný, když je NP-těžky a náleží do třídy NP. Problém Q nazveme NP-těžkým, pokud každý problém ve třídě NP lze na problém Q polynomiálně převést, tedy pokud platí ∀P ∈ NPTIME : P ⊳ Q.
Problém Q nazveme NP-úplným, pokud je NP-těžký a náleží do třídy NP.
NP-úplné problémy:
- SAT - problém splnitelnosti booleovských formulí
- 3-SAT (problém SAT s omezením na 3 literály) - je splnitelná boolovská formule v konjuktivní normální formě, kde každá klauzule obsahuje právě tři literály?
- CG - barvení grafu k barvami
- 3-CG - barvení grafu třemi barvami
- HK, HC - hamiltonovské kružnice, cyklu
- Subset-Sum - množina součtů
- TSP - problém obchodního cestujícího (Ano/Ne verze) - lze objet n měst a neujet víc než danou vzdálenost?
- ILP (problém celočíselného lineárního programování)
Vstup: Matice A typu m × n a sloupcový vektor b velikosti m, jejichž prvky jsou celá čísla.
Otázka: Existuje celočíselný sloupcový vektor x (velikosti n) tž. Ax ≥ b?