Означает ли тот факт, что проблема полна по времени EXP, означает, что A не находится в D T I M E ( 2 o ( n ) ) ?
Мне известно, что по теореме временной иерархии не входит в E = D T I M E ( 2 O ( n ) ) . Тем не менее это, по-видимому, не исключает немедленного существования субэкспоненциальных алгоритмов времени для каждой EX-полной задачи A , поскольку при сокращении экземпляра x задачи B ∈ E X Pв случае у проблемы , мы можем иметь полиномиальное увеличение размера. Другими словами, | у | = | х | O ( 1 ) .
Поэтому мой вопрос заключается в том, существует ли какой-либо аргумент, который безоговорочно исключает существование субэкспоненциальных временных алгоритмов для задач, полных на ЕХР.
exp-time-algorithms
complexity
проверка
источник
источник
Ответы:
Из-за широкого спроса я конвертирую свой комментарий в ответ.
Простой аргумент заполнения показывает, что для каждой константы существуют задачи, полные EXP, в D T I M E ( 2 n ϵ ) . Действительно, исправим произвольную EX-полную задачу L и предположим, что она вычислима за время 2 n c . Пусть d > c / ϵ и рассмотрим задачу L ′ = { 0 m # w : w ∈ L , m ≥ | ш |ε > 0 D T I M E ( 2Nε) L 2Nс d> C / ε
С одной стороны,Lполиномиального времени
С другой стороны, вычислимо за время 2 n ϵ : учитывая ввод размера n , мы сначала проверяем (за полиномиальное время), что он имеет вид 0 m # w для m ≥ n ′ d , где n ′ = | ш | , Затем мы проверяем, если w ∈ L , что занимает время 2 n ′ c ≤ 2 m c / d ≤ 2 m ϵ ≤ 2 nL′ 2nϵ n 0m#w m≥n′d n′=|w| w∈L .2n′c≤2mc/d≤2mϵ≤2nϵ
источник