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.

Given a decision problem X, can there exist an algorithm A which, given any algorithm B which solves X in finitely many steps, determines whether B runs in polynomial time? If such an A exists, when is it possible for A to run in polynomial time?

share|improve this question
    
I don't think this qualifies as a soft question. I'll remove the tag if no one objects. –  Goos Jun 3 '13 at 3:33

1 Answer 1

up vote 4 down vote accepted

For some decision problems $X$, the answer to your question is affirmative, for the trivial reason that $X$ admits no polynomial-time solution, so $A$ can be the algorithm that always says "no". But for more reasonable problems $X$, there cannot be any such $A$.

Consider a problem $X$ for which there is a polynomial-time algorithm $Q$ that decides $X$. I claim that, if there were an $A$ as in your question, we could use it to decide the halting problem. To see this, consider any instance of the halting problem, say Turing machine $M$ on input $z$. Let $B$ be the following algorithm for solving the problem $X$. On any input $x$, first use $Q$ to figure out the answer, but, instead of outputting the answer immediately, do two tasks in parallel: (1) count from 1 to $2^n$, where $n$ is the length of $x$, and (2) run $M$ on input $z$. As soon as either of these tasks is finished, output the answer that $Q$ gave. If machine $M$ on input $z$ doesn't halt, then task (2) will never be completed, so $B$ will produce an output only after exponential time $2^n$. But if $M$ on $z$ halts after $s$ steps, then $B$ will produce its output after a polynomial number of steps, essentially the time needed by $Q$ plus (a constant overhead factor times) $s$. So $B$ takes polynomial time iff $M$ on $z$ halts.

Now the program for $B$ can be effectively computed from that of $M$ and $z$. So by producing $B$ and then applying the assumed algorithm $A$ to it, we could decide the halting problem. Since the halting problem is known to be undecidable, it follows that there cannot be such an $A$.

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.