# EXP-Complete Problems vs Subexponential Algorithms

Does the fact that a problem $A$ is EXP-time complete implies that $A$ is not in $DTIME(2^{o(n)})$?

I'm aware that by the time hierarchy theorem, $EXP=DTIME(2^{n^{O(1)}})$ is not included in $E=DTIME(2^{O(n)})$. Nevertheless this does not seem to exclude immediately the existence of sub-exponential time algorithms for every EXP-complete problem $A$, since when reducing an instance $x$ of a problem $B\in EXP$ to an instance y of problem $A$, we may have a polynomial blow up in size. In other words, $|y|=|x|^{O(1)}$.

So my question is whether there exists some argument that rules out, unconditionally, the existence of sub-exponential time algorithms for EXP-complete problems.

• On the contrary, a trivial padding argument shows that for every $\epsilon>0$, there exist EXP-complete problems computable in time $2^{n^\epsilon}$. Oct 12, 2016 at 8:06
• @EmilJeřábek Thanks. I guess your comment is the answer I was looking for. Could you please expand it into an answer? Oct 12, 2016 at 13:47

A simple padding argument shows that for every constant $\epsilon>0$, there exist EXP-complete problems in $\mathrm{DTIME}(2^{n^\epsilon})$. Indeed, fix an arbitrary EXP-complete problem $L$, and assume that it is computable in time $2^{n^c}$. Let $d>c/\epsilon$, and consider the problem $$L'=\left\{0^m\#w:w\in L,m\ge|w|^d\right\}.$$ On the one hand, $L$ is polynomial-time${}^\dagger$ reducible to $L'$ via the function $w\mapsto0^{|w|^d}\#w$, thus $L'$ is EXP-hard.
On the other hand, $L'$ is computable in time $2^{n^\epsilon}$: given an input of size $n$, we first check (in polynomial time) that it is of the form $0^m\#w$ for $m\ge n'^d$, where $n'=|w|$. Then we check if $w\in L$, which takes time $2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$.
${}^\dagger$ Actually, the reduction as given is even uniform $\mathrm{AC}^0$, and it can be made DLogTime if we replace $|w|$ with an upper bound that is a power of two.