Экспоненциальная сложность

Задачи с экспоненциальной сложностью времени работы образуют класс EXPTIME, в формально определяемый как:

${\displaystyle {\text{EXPTIME}}=\bigcup _{k=1}^{\infty }TIME\left(2^{n^{k}}\right)}$,

где ${\displaystyle TIME(f(n))}$ — множество задач, которые могут быть решены алгоритмами, время работы которых ограничено сверху функцией ${\displaystyle f(t)}$^[4].

Принято считать, что алгоритмы с полиномиальной сложностью являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Однако, это предположение не совсем точное. Дело в том, что время работы алгоритма зависит от значения n (размерности задачи) и сопутствующих констант скрытых в O-нотации. В некоторых случаях для малых значений n полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений n время работы алгоритма с экспоненциальной сложностью существенно больше.

Существуют алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («суб-экспоненциальное»). Примером такой задачи является разложение целого числа на простые множители (факторизация). Такие алгоритмы также относятся к «медленным».