3
$\begingroup$

I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press. I cannot solve the first problem in Chapter Three(p.77), which may be probably disappointing. The problem is as follow:

Show that the follow language is undecidable:
{M|M is a machine that runs in $100n^2+200$ time}.

3 Answers 3

4

You can reduce the halting problem to your problem. Given a Turing machine $M$ and input $z$, let us design a new machine $N$, which on input $y$, first runs $M$ on input $z$ for $|y|$ steps, and if this doesn't halt yet, then $N$ halts, but if $M$ does halt, then $N$ counts up to $|y|^3$ and then halts. That is, if $M$ doesn't halt on $z$, then $N$ halts quickly, but if $M$ does halt on $z$, then $N$ takes a long time on large input.

Thus, $M$ fails to halt on $z$ if and only if $N$ runs in $100n^2+200$ time on all input of size $n$. So if we could decide the latter property, then we could decide the halting problem, which is impossible.

This argument actually shows more, namely, that the complement of the halting problem is $1$-reducible to the running-in-time-$f$ problem.

(A similar argument could make use of Yuval's suggestion, using the halting-on-empty-string problem instead of the halting problem, which would eliminate the need to consider nontrivial $z$.)

  • 0
    Joel, there are a lot of tiny details --- I still do not see why the empty tape is important here. I also do not think that the halting problem is reductible to this one, as, if I am not mistaken, the later is just $\Pi_1^0$-complete.2011-05-04
  • 0
    The empty tape is not important. I have edited to explain how to reduce the full halting problem. The given problem is Turing equivalent to the halting problem, since we have reduced the halting problem to it, and clearly it reduces to the halting problem.2011-05-04
  • 0
    The argument works with almost any computable function $f(n)$. It is easiest if $n\lt f(n)$, since then it is easy to simulate $M$ on $z$ for $|y|$ steps on input $y$ without exceeding $f(|y|)$, but one can generalize to other $f$.2011-05-04
  • 0
    I do not understand your sentence "That is, if M doesn't halt on z, then N halts quickly" --- should not it be "That is, if M doesn't halt on z in |y| steps, then N halts quickly", or am I missing something?2011-05-04
  • 1
    And the problem is obviously in $\Pi_1^0$ --- you can construct a machine that for a given machine $M$ simulates it on every input $x$ for $100|x|^2 + 200$ steps. If $M$ exceeds this number of steps on any input than $M$ just halts and sayes "yes". So if your argument were correct it would mean that the above problem is \emph{recursive}.2011-05-04
  • 0
    Fallen, note that from the perspective of $N$, the machine $M$ and $z$ are constant. If $M$ doesn't halt on $z$, then for no $y$ will $N$ see it to halt in $|y|$ steps, and so $N$ will halt on every $y$ in $|y|$ steps. So $N$ will be in the desired set. But if $M$ does halt on $z$, then for large $y$ the machine $N$ will see that, and then purposfully take too long. So in this case, $N$ will not be in the desired set. So it is a reduction.2011-05-04
  • 1
    About your $\Pi^0_1$ remark, it is resolved by observing that my argument reduces the *complement* of the halting problem to the given problem. (I was missing a complement, and have edited.) But this is fine for Turing reduction, since if we can decide a set, we can decide its complement.2011-05-04
  • 0
    Ok, but now it is just exactly the same solution as mine :-)2011-05-04
  • 0
    Now that I read your solution again, I see that there is a resemblence, but I confess that I did not understand your answer upon reading it the first few times.2011-05-04
  • 0
    Joel, your solution is clearer because (as I have mentioned in a very first comment) you have skipped "tiny details", and, even after all corrections, your solution is still(!) a bit incorrect. BTW, your more general problem follows easily from Rice's theorem, no?2011-05-04
  • 0
    I'm happy to correct any remaining errors or add whatever details might be necessary...2011-05-04
  • 0
    Joel, you will find some of them in my sketch of a proof.2011-05-04
  • 0
    One of the aspects you have ignored is that the running time of $N$ is not $100n^2+200$ but $k*n+c$, for some constants $k$ and $c$, if $M$ halts, and $k*n+c + n^3$ if $M$ does not, so there could be two problems: a) you will get wrong answers for an initial segment of data, b) these constants may depend on $M$ or $z$.2011-05-04
  • 0
    And, of course, you *cannot* recursively reduce (did you write about other reductions???) the halting problem to this one, as I have said about a dozen of times...2011-05-04
  • 1
    I understood the problem to mean that the running time should be *at most* $f(n)$, rather than exactly $f(n)$. (And we can easily arrange that $N$ simply ignores all small input.) About your reduction comment, my argument shows that the halting problem is Turing reducible to the running-time problem. That is, from an oracle for the running-time problem, we can decide the halting problem. It follows that the running-time problem is not decidable. But my argument shows more precisely that the complement of the halting problem $1$-reduces to the running-time problem, which is a stronger result.2011-05-04
  • 1
    In particular, yes, my solution mentions two different reductions: the (Turing) reduction of the halting problem to the running time problem, and the $1$-reduction of the complement of the halting problem to the running time problem.2011-05-04
  • 0
    The running time problem is also 1-reducible to the complement of the halting problem, as follows: given a machine $M$, make a machine $N_M$ that runs $M$ successively on inputs 1, 2, 3, 4, 5, ..., and if $M$ ever fails to halt in the prescribed number of steps for that input then $N_M$ immediately halts. Thus $N_M$ never halts if and only if $M$ follows the desired time bound for all inputs. It's interesting that the choice of any specific time bound makes the set $\Pi^0_1$; the more general question whether $M$ is $O(n^2)$ is, I believe, $\Sigma^0_2$, even if we assume $M$ is total.2011-05-04
  • 1
    Yes, in fact every $\Pi^0_1$ question similarly $1$-reduces to the complement of the halting problem. I agree with what you say about $O(n^2)$, and indeed, the set of such $M$ is $\Sigma^0_2$-complete. This seems to work even with $O(f)$ for any non-zero $f$, even $O(1)$, since the big-O concept in effect adds an extra quantifier.2011-05-04
3

Hint: It is undecidable whether $M$ halts when running on the empty string.

-1

I am wondering if this is a correct answer:

Suppose input x that is provided to Turing machine M is of infinite length and therefore n is infinite. Then for every every pair M and x, the problem becomes an instance of the halting problem and hence is unsolvable.