EXP-Complete Problems vs. Subexponential Algorytmy

Czy fakt, że problem jest zakończony w czasie EXP, sugeruje, że nie występuje w ? $A$ $A$ $DTIME(2^{o(n)})$

Wiem, że według twierdzenia o hierarchii czasu nie jest uwzględnione w . Niemniej jednak wydaje się, że nie wyklucza to natychmiastowego istnienia sub wykładniczych algorytmów czasowych dla każdego problemu pełnego EXP , ponieważ przy zmniejszeniu wystąpienia problemu $EXP=DTIME(2^{n^{O(1)}})$ $E=DTIME(2^{O(n)})$ $A$ $x$ $B\in EXP$ na przykład y problemu , możemy mieć wielomianowy wysadzenie. Innymi słowy, . $A$ $|y|=|x|^{O(1)}$

Moje pytanie brzmi więc, czy istnieje jakiś argument, który bezwarunkowo wyklucza istnienie sub wykładniczych algorytmów czasowych dla problemów z pełnymi EXP.

exp-time-algorithms complexity weryfikacja
źródło

Przeciwnie, trywialny argument wypełniający pokazuje, że dla każdego

istnieją problemy z pełnymi EXP obliczalnymi w czasie

ϵ > 0

$\epsilon>0$

2^{n^{ϵ}}

$2^{n^\epsilon}$

Emil Jeřábek

@ EmilJeřábek Thanks. Chyba twój komentarz jest odpowiedzią, której szukałem. Czy możesz rozwinąć tę odpowiedź?

weryfikacja

Odpowiedzi:

Ze względu na powszechne zapotrzebowanie przekształcam mój komentarz w odpowiedź.

$\epsilon>0$ $\mathrm{DTIME}(2^{n^\epsilon})$ $L$ $2^{n^c}$ $d>c/\epsilon$

L^{'} = {0^{m} # w : w \in L, m \geq | w |^{d}} .

$L'=\left\{0^m\#w:w\in L,m\ge|w|^d\right\}.$

L

$L$

^{†}

${}^\dagger$

L^{'}

$L'$

w \mapsto 0^{| w |^{d}} # w

$w\mapsto0^{|w|^d}\#w$

L^{'}

$L'$

$L'$ $2^{n^\epsilon}$ $n$ $0^m\#w$ $m\ge n'^d$ $n'=|w|$ $w\in L$ $2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$

${}^\dagger$ $\mathrm{AC}^0$ $|w|$

Emil Jeřábek
źródło