According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$ into $L$ in polynomial time. I believe this definition is fine but I have some observation that are confusing me. I construct a language $L''$ in $EXP$ such that $L''$ can not be convert into $L$ with polynomial time reductions and $L''$ is in $EXP$ with an algorithm M in this way:

let $f_i$ be the iteration of all reductions.

1) $input(i,x)$

2) run $f_i(i,x)$ in time at most $2^n$ if the computation time is greater than $n^{\log n}$ then accept.

3)else accept $(i,x)$ iff $f_i(i,x) \not \in L$.

Obviously $Language(M) \in EXP$ so there exists a polynomial time reduction from $Language(M)$ to $L$ but this makes a contradiction because M prevents the reductions of less than $n^{\log n}$ time to $L$ and it is because of line 3 of algorithm.suppose $f_j$ is polynomial reduction, the membership of $(i,x)$ in $L(M)$ is the opposite of the member ship of $f_j(j,x)$ so $f_j$ is not a reduction from L(M) to L by the line 3 of algorithm.

My question is: where is my mistake?


1 Answer 1


Are every problems in EXP karp reducible to any EXP-Complete?

Yes. That's the definition of $\mathrm{EXP}$-completeness.

My question is: where is my mistake?

Your mistake is in believing that $L''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you mean by "$M$ prevents the reductions" – you're trying to reduce from $L(M)$ to $L$, not from $L$ to $L(M)$.

On the other hand, $L''$ is not $\mathrm{EXP}$-complete, by the time hierarchy theorem. Any language reducible to $L''$ must be in time $O(2^{(\log (n^c))^2})$ for some $c$, but this is just time $O(2^{(c\log n)^2})=O(2^{(\log n)^2})$.

  • $\begingroup$ Thank you for quick answer. If reduction $f_j(j,x)$ runs in polynomial time for example $n^2$ according to line 3 of algorithm the membership of $(j,x)$ in $L(M)$ will be the opposite of the membership of $f_j(j,x)$ in L so $f_j$ is not a reduction. I think this force the $f_j$ to not be a reduction from L(M) to L and by the limitation of time $n^{\log n}$ the algorithm prevents all polynomial reductions and my exact problem is here. $\endgroup$ Aug 18, 2019 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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