Optimizavimo sudetingumas

Algoritmas polinominis, kai skaiciavimo laikas
$T = C m^K$.
Cia
$K$ sveikas skaicius,
$m$ uzdavionio sudetingumas.
Diskretiniu atveju, $m$ kintamuju skaicius.
Tolydiniu atveju, $m$ garantuotas tikslumas,
kai maksimali paklaida $\epsilon \le 2^{-m}$.
Algoritmas eksponentinis, kai skaiciavimo laikas
$T \ge C 2^m$.
"Ribiniu" atveju tai $NP$-pilna klase.
Ši klase pasizymi tuo, kad nera irodyta ar cia butinai reikia eksponentinio algoritmo,
ar uztenka ir polinominio.
Polinominio algoritmo $NP$-pilnai klasei
dar niekas nesugalvojo,
taciau neirodyta, kad jo nera.