1
$\begingroup$

It's well known $EXP$ is closed under polynomial reduction. It means $\bigcup_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$? Is it also closed under polynomial reduction?

$\endgroup$
2
$\begingroup$

No, this would contradict the time hierarchy theorem. Note that any language in $\mathsf{EXP}$ is polynomial time reducible to some language in $\mathsf{E}$ by padding. Suppose $L\in \mathsf{DTIME\big(2^{n^c}\big)}$, then consider $L'=\big\{x0^{|x|^c}\big|x \in L\big\}$. Obviously $L'\in \mathsf{E}$ and $L\le_p L'$, thus if $\mathsf{E}$ is closed under polynomial time reductions we have $L\in\mathsf{E}$ and consequently $\mathsf{E=EXP}$.

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