Problém P versus NP: Porovnání verzí

[[Třída složitosti]] '''P''' obsahuje všechny úlohy, jejichž řešení lze nalézt [[Determinismus|deterministickým]] [[Turingův stroj|Turingovým strojem]] v [[Asymptotická složitost|polynomiálním]] čase. Pro třídu '''NP''' platí totéž s tím rozdílem, že se jedná o ''nedeterministický'' Turingův stroj. Jsou to ty problémy, jejichž řešení lze ''ověřit'' v polynomiálním čase, ovšem nevíme, zda je lze také v polynomiálním čase ''nalézt''. Pak ale nevíme, co bychom mohli ověřovat. Stejně nikdo neví, jak by mělo ověření vypadat. Zbývá matematický důkaz.