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?
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"&nbsp;&ndash; you're trying to reduce from $L(M)$ to&nbsp;$L$, not from $L$ to&nbsp;$L(M)$.

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