Problemas completos de EXP versus algoritmos subexponenciales

¿El hecho de que un problema esté completo en el tiempo EXP implica que no está en ? $A$ $A$ $DTIME(2^{o(n)})$

Soy consciente de que, según el teorema de la jerarquía temporal, no está incluido en . Sin embargo, esto no parece excluir inmediatamente la existencia de algoritmos de tiempo sub-exponenciales para cada problema completo de EXP , ya que al reducir una instancia de un problema $EXP=DTIME(2^{n^{O(1)}})$ $E=DTIME(2^{O(n)})$ $A$ $x$ $B\in EXP$ para una instancia y del problema , podemos tener una explosión polinómica de tamaño En otras palabras, . $A$ $|y|=|x|^{O(1)}$

Entonces mi pregunta es si existe algún argumento que descarte, incondicionalmente, la existencia de algoritmos de tiempo sub-exponenciales para problemas completos de EXP.

exp-time-algorithms complexity verificar
fuente

Por el contrario, un argumento de relleno trivial muestra que por cada

, existen problemas de EXP-completa computables en el tiempo

ϵ > 0

$\epsilon>0$

2^{n^{ϵ}}

$2^{n^\epsilon}$

Emil Jeřábek

@ EmilJeřábek Gracias. Supongo que tu comentario es la respuesta que estaba buscando. ¿Podría por favor ampliarlo en una respuesta?

verificar el

Respuestas:

Debido a la demanda popular, estoy convirtiendo mi comentario en una respuesta.

$\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
fuente