10
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.