NP-completeness
NP-úplnost je koncept v teorii počítačové vědy, který se týká klasifikace problémů podle jejich složitosti. Problémy, které jsou zařazeny do třídy NP (nondeterministic polynomial time), jsou takové, pro které lze ověřit možné řešení v polynomiálním čase. Problém se považuje za NP-úplný, pokud patří do třídy NP a pokud lze každý problém z NP na něj redukovat v polynomiálním čase. To znamená, že NP-úplné problémy jsou nejzákladnější problémy v NP, a pokud je možné je vyřešit v polynomiálním čase, pak je možné vyřešit všechny problémy v NP také v polynomiálním čase. NP-úplnost byla poprvé definována Stephenem Cookem v roce 1971 a je klíčovým tématem v oblasti teorie složitosti a informatiky. Příklady NP-úplných problémů zahrnují problém obchodního cestujícího, problém 3-satisfiability a mnoho dalších. Řešení NP-úplného problému by mělo dalekosáhlé důsledky pro počítačovou vědu a matematiku, zejména v oblasti algoritmů a optimalizace.