Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top