4
$\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$.)

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