Redukce je základním nástrojem pro porovnání složitosti dvou problémů. S redukcí jsme se už setkali v souvislosti s vyčíslitelností problémů. Víme, že redukce konstruuje z případů jednoho problému ekvivalentní případy druhého problému. V této kapitole navíc požadujeme, aby tato konstrukce proběhla v polynomiálním čase. Redukce je základem pro definici třídy tzv. C-úplných problémů, kde C je složitostní třída. 

Nejdůležitější fakta k zapamatování (C je některá z tříd P, NP, EXPTIME, NEXPTIME, PSPACE):

• A ≤ B intuitivně znamená, že problém B je nejméně tak těžký jako A
  
• pokud A ≤ B, a problém B patří do třídy C, tak i problém A patří do třídy C
  
• každý C-těžký problém je nejméně tak těžký jako kterýkoli problém ve třídě C
  
• C-těžký problém ale sám do třídy C patřit nemusí (může patřit do větší třídy obsahující C)
• pokud A ≤ B, a A je C-těžký, tak i B je C-těžký
  
• pokud C-těžký problém patří do třídy C, tak je C-úplný
  
• C-úplné problémy jsou ty nejtěžší ve třídě C, a jsou všechny vzájemně redukovatelné
  
• když chceme ukázat o nějakém problému B ze třídy C, že je C-úplný, tak stačí vzít vhodný C-úplný problém A a sestrojit redukci A ≤ B

Největší praktický význam má třída NP-úplných problémů, kam patří velké množství v praxi řešených problémů (optimalizační, dopravní, síťové...). Nejznámějšími reprezentanty jsou problém SAT a HAM (známý též jako problém obchodního cestujícího). Příklady dalších NP-úplných problémů naleznete v tématu "Základní složitostní třídy".

Všechny NP-úplné problémy se v praxi považují za nezvládnutelné - na počítači jsme většinou schopni najít jen jejich přibližná řešení, přesná řešení jsou příliš výpočetně náročná.