# Halting problem in EXP-complete

I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:

It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

Why does encoding in $$O(\log k)$$ makes it exponential?
How can we reduce the other problems to our halting problem?

You are referring to the following problem: $$H = \{ (\langle M \rangle, w, t) \mid \text{M accepts w in time at most t} \}$$ where $$t$$ is binary encoded. You should note this is not the (classical) halting problem, but, rather, the bounded version of the halting problem. The halting problem itself cannot be complete for $$\mathsf{EXP}$$ (or any other subclass of the recursive languages).
Now, to answer your question. First, notice that, because $$t$$ is encoded in binary, the input has length $$|\langle M \rangle| + |w| + \log t$$. To simulate $$M$$ on $$w$$ for $$t$$ steps we can use a universal TM, which takes time $$O(t \log t)$$. Since we are doing a worst-case analysis, we can afford to view $$|\langle M \rangle|$$ as constant. Also, because $$t \in O(2^{p(|w|)})$$ for some polynomial $$p$$, $$\log t \in O(p(|w|))$$. Hence, the input has size $$O(|w| + p(|w|))$$ while our simulation takes time $$O(t \log t) \subset O(p(|w|) 2^{p(|w|)})$$ and, in turn, $$p(|w|) 2^{p(|w|)} \in 2^{\textrm{poly}(|w|)}$$. This proves $$H \in \mathsf{EXP}$$.
Reducing a problem $$P \in \mathsf{EXP}$$ to $$H$$ is also very simple: If $$P$$ is decidable by $$M$$ in time bounded by a function $$f \in 2^{\textrm{poly}(n)}$$, then any instance $$x$$ of $$P$$ is a yes-instance if and only if $$(\langle M \rangle, x, f(|x|)) \in H$$, where $$f(|x|)$$ is given binary encoded. The time taken by this reduction is dominated by computing $$f(|x|)$$, which can be performed in time polynomial in $$|x|$$ (by first converting it to binary and then computing $$f(|x|)$$ in polynomial time).
• To prove this problem is in $EXP$, is it not sufficient to state that, in the worst case, the problem would take $t$ time, which is exponential to the number of bits used to store $t$? – J. Schmidt Aug 12 at 9:17
• @J.Schmidt That is the gist of it. However, note we cannot really expect to solve instances of $H$ always in time $t$ with a single Turing machine. There is always the $\log t$ slack factor involved because of the simulation of $M$. (If we could avoid this slack factor, then we could also strengthen the time hierarchy theorem, for example.) – dkaeae Aug 12 at 9:26
• @dfsh That follows from the definition of $\mathsf{EXP}$. It contains all problems solvable in $2^{\text{poly}(n)}$ time (by definition). – dkaeae Aug 12 at 13:10