EXP-полные задачи против субэкспоненциальных алгоритмов

10

Означает ли тот факт, что проблема полна по времени EXP, означает, что A не находится в D T I M E ( 2 o ( n ) ) ?AADTIME(2o(n))

Мне известно, что по теореме временной иерархии не входит в E = D T I M E ( 2 O ( n ) ) . Тем не менее это, по-видимому, не исключает немедленного существования субэкспоненциальных алгоритмов времени для каждой EX-полной задачи A , поскольку при сокращении экземпляра x задачи B E X PEXP=DTIME(2nO(1))E=DTIME(2O(n))AxBEXPв случае у проблемы , мы можем иметь полиномиальное увеличение размера. Другими словами, | у | = | х | O ( 1 ) .A|y|=|x|O(1)

Поэтому мой вопрос заключается в том, существует ли какой-либо аргумент, который безоговорочно исключает существование субэкспоненциальных временных алгоритмов для задач, полных на ЕХР.

проверка
источник
11
Напротив, тривиальный аргумент заполнения показывает, что для каждого существуют EXP-полные задачи, вычислимые за время 2 n ϵ . ϵ>02nϵ
Эмиль Йержабек
7
@ EmilJeřábek Спасибо. Я думаю, ваш комментарий - это ответ, который я искал. Не могли бы вы расширить его в ответ?
проверка

Ответы:

12

Из-за широкого спроса я конвертирую свой комментарий в ответ.

Простой аргумент заполнения показывает, что для каждой константы существуют задачи, полные EXP, в D T I M E ( 2 n ϵ ) . Действительно, исправим произвольную EX-полную задачу L и предположим, что она вычислима за время 2 n c . Пусть d > c / ϵ и рассмотрим задачу L = { 0 m # w : w L , m | ш |ϵ>0DTIME(2nϵ)L2ncd>c/ϵ С одной стороны,Lполиномиального времени

L={0m#w:wL,m|w|d}.
L сводится к L через функцию w 0 | ш | d # w , таким образом, L ' EXP-труден.Lw0|w|d#wL

С другой стороны, вычислимо за время 2 n ϵ : учитывая ввод размера n , мы сначала проверяем (за полиномиальное время), что он имеет вид 0 m # w для m n d , где n = | ш | , Затем мы проверяем, если w L , что занимает время 2 n c2 m c / d2 m ϵ2 nL2nϵn0m#wmndn=|w|wL .2nc2mc/d2mϵ2nϵ


AC0|w|

Эмиль Йержабек
источник