Polinomsal zamanda

Polinomsal zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğuna göre en fazla bir polinom tane adımda çözebildiği bir problemdir.

Polinomsal zaman, daha basit bazı zamanlara ayrılabilir:

Sabit zaman
Lineer zaman
İkinci derece zaman
vs.