<p>Due to popular demand, I’m converting my comment to an answer.</p>

<p>A simple padding argument shows that for every constant $\epsilon&gt;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&gt;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.</p>

<p>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}$.</p>

<hr>

<p>${}^\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.</p>

CC BY-SA 3.0
2016-10-25T15:53:38.920Z
2016-10-25T15:53:38.920Z
Emil Jeřábek
<p>Does the fact that a problem $A$ is EXP-time complete implies that $A$ is 
not in $DTIME(2^{o(n)})$? </p>

<p>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)}$. </p>

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

CC BY-SA 3.0
2016-10-12T08:06:43.637Z
On the contrary, a trivial padding argument shows that for every $\epsilon>0$, there exist EXP-complete problems computable in time $2^{n^\epsilon}$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-12T13:47:49.587Z
@EmilJeřábek Thanks. I guess your comment is the answer I was looking for. Could you please expand it into an answer?
verifying
<exp-time-algorithms><complexity>
EXP-Complete Problems vs Subexponential Algorithms
verifying
# EXP-Complete Problems vs Subexponential Algorithms

(Asked by: username_0 on 2016-10-12)

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.

**Tags:** exp-time-algorithms, complexity

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

---

## 1 answers

### Answer by username_1 on 2016-10-25. Score: 12 | Accepted answer

Due to popular demand, I’m converting my comment to an answer.

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.


---

