Pokud je časová složitost f(N) [[polynom]], hovoříme o polynomiálně omezených algoritmech. Takové problémy, které řeší nějaký polynomiální algoritmus, patří do tzv. '''[[P_(třída_složitosti)|třídy P]]'''.
Pokud pro daný problém neexistujeexistuje polynomiálně omezený [[algoritmus]], který řešeníověří nalezne,správnost aleřešení existuje(dodaného polynomiálněněkým omezený algoritmus, který řešení ověříjiným), hovoříme o [[nedeterministicky polynomiální problém|nedeterministicky polynomiálníchpolynomiálním problémechproblému]].Problémy(polynomiálně omezený algoritmus, kterékterý řešířešení nedeterministickýtohoto algoritmusproblému dokáže nalézt, patřízde obecně existovat nemusí). Tyto problémy dotvoří '''[[NP_(třída_složitosti)|třídytřídu NP]]'''. Ekvivalentně lze tuto třídu definovat jako množinu problémů, které lze řešit na [[Nedeterministický Turingův stroj|nedeterministickém Turingově stroji]] v polynomiálně omezeném čase. Do třídy NP patří (např. [[problém obchodního cestujícího]], splnitelnost [[formule výrokové logiky]] a mnoho dalších), včetně všech problémů z třídy P.
Jednou z největších současných otevřených otázek teoretické [[informatika|informatiky]] je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz [[NP-úplnost]] a [[problém P versus NP]]).
