Üstel zaman

Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla ${\displaystyle e^{p(n)}\,}$ katı tane adımda çözebildiği bir problemdir (p, herhangi bir polinom olabilir). Doğal olarak, üstel zaman polinomsal zamanı içine alabilir.

Örneğin, gezgin satıcı problemini mümkün olan tüm turları teker teker hesaplayıp çözmek üstel zaman alacaktır, zira ${\displaystyle n\,}$ şehir için ${\displaystyle n!\,}$ tur vardır...