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

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?

Yes. That's the definition of $$\mathrm{EXP}$$-completeness.
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})$$.
• 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. Aug 18 '19 at 9:59