algorithm to determine complexity of algorithms?

Question

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?

Answer 1

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