Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

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

share|improve this answer
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}. –  Michal R. Przybylek May 4 '11 at 13:55
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. –  JDH May 4 '11 at 14:06
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. –  JDH May 4 '11 at 16:50
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. –  JDH May 4 '11 at 17:27
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. –  JDH May 4 '11 at 20:20

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.