Poly-time reductions for proving EXPTIME-hardness are _not_ enough?

Question

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}|})$?

Answer 1

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.