2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – J. Schmidt Aug 12 at 9:17
  • 1
    $\begingroup$ @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.) $\endgroup$ – dkaeae Aug 12 at 9:26
  • $\begingroup$ Might I ask why t is in O(2^p(|w|))? @dkaeae $\endgroup$ – dfsh Aug 12 at 12:09
  • $\begingroup$ @dfsh That follows from the definition of $\mathsf{EXP}$. It contains all problems solvable in $2^{\text{poly}(n)}$ time (by definition). $\endgroup$ – dkaeae Aug 12 at 13:10

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.