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úlohy jednájsou ořešitelné ''nedeterministickýnedeterministickým'' TuringůvTuringovým strojstrojem, který náhodně vybírá potenciální řešení úlohy a v polynomiálním čase ověřuje jejich správnost. Jsou to tedy 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''.