Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me.

Suppose our problem can be solved in time $O(2^k)$, where $k$ is an input number to our problem instance; let it be in binary. Consider some EXPTIME-complete problem that takes a number $n$ as input. Consider a hypothetical reduction that creates our problem instance with $k=2^n$; it is is poly-time, because it computes $2^n$ by shifting $n$ times the letter $1$ to the right. Our reduction implies that the original problem can be solved in $2^{2^n}$ time. But that is not sufficient for proving EXPTIME-hardness of our problem, because we cannot derive the contradiction by assuming our problem is solveable in poly-time. Therefore, we cannot use poly-time reductions.

Where is the mistake? Is it about binary/unary encoding of numbers? Is it about meaning of $O(2^k)$ vs. $O(2^{|\text{string representing k}|})$?


If your problem can be solved in time $O(2^k)$, where $k$ is some number in the input, all you can say about its membership in conventional complexity classes is that it's in $\mathrm{2EXP}$, since an instance of length $\ell$ can be decided in time $O(2^{2^\ell})$. You've not established that the problem is in $\mathrm{EXP}$.

$\mathrm{EXP}$, like all conventional complexity classes, is defined in terms of the length of the input, not the values represented in that input.

| cite | improve this answer | |

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.