Что такое субэкспоненциальная сложность?

Вопрос. Что такое субэкспоненциальная сложность? Какие алгоритмы имеют субэкспоненциальную сложность?

При всей простоте вопроса ответ на него неоднозначен.

Математически корректное определение субэкспоненциальной сложности — это все, что вычислимо за время порядка $2^{o(n)}$. В главе 4 книги «Введение в криптографию» Ю. В. Нестеренко пишет, что субэкспоненциальные функции — это все функции, которые растут медленнее любой степенной. Заметим, что здесь, как и во многих работах по алгоритмической теории чисел, аргументом функции сложности является не длина входа, а сам вход.

Проблема в том, что существует другое определение субэкспоненциальной сложности — все, что вычислимо за время порядка $2^{n^{o(1)}}$. Это определение используется, в частности, в работах по дерандомизации вероятностных алгоритмов. Есть и соответствующий сложностной класс $SUBEXP=\bigcap _{\varepsilon >0} DTIME(2^{n^\varepsilon})$.

Ситуация, в целом, типичная для теории сложности вычислений. Например, аналог класса $P$ для экспоненциального времени определяется неоднозначно. Есть два класса: $E=DTIME(2^{O(n)})$ и $EXP=\bigcup _k DTIME(2^{n^k})$.

Однако, в случае субэкспоненциальной сложности у второго из определений есть существенный дефект: между экспоненциальной и субэкспоненциальной сложностями должна существовать еще какая-то промежуточная сложность.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна