<p>It might not be the Halting Problem exactly, but it is also not possible to decide if a given algorithm runs in polynomial time or not. The reason is the same as many other undecidable problems; using Kleene's Recursion theorem, an algorithm can always query if itself is a polynomial time algorithm, and can adopt the opposite behavior.</p>

<p>Example properties of algorithms that <em>are</em> decidable are things such as:</p>

<ul>
<li>If an algorithm's source code has less than 1000 characters</li>
<li>If an algorithm, on a given input $x$, will halt within 500 steps</li>
<li>If an algorithm's source code has a particular symbol in it</li>
</ul>

<p>That is, properties of an algorithm that have nothing to do with its execution (or only a limited part of its execution) tend to be decidable, while any nontrivial property of a program's execution will likely be undecidable.</p>

<p>Also, in general, <em>any</em> property of an algorithm related to its output is undecidable (this is formalized by Rice's theorem), although running time is not a property of its output.</p>

CC BY-SA 3.0
2015-02-22T06:09:34.860Z
I agree with you philosophically, but is Rice's theorem really applicable to the question? Rice's theorem, in the statement I am familiar with, talks about the decidability of the problem "Does the language decided by Turing machine $M$ have property $P$?". This does not capture questions about the running time of $M$.
Sasho Nikolov
CC BY-SA 3.0
2015-02-22T06:27:07.543Z
@SashoNikolov: I think Rice's theorem does apply. The formal statement of Rice's theorem says that it's undecidable to determine whether the language a TM computes is in C for any non-trivial complexity class C. Here non-trivial means that there exists a TM deciding a language in C, and a TM deciding a language not in C. Clearly this holds when C = P.
Huck Bennett
CC BY-SA 3.0
2015-02-22T06:34:10.747Z
@HuckBennett P is non-trivial but the problem you are describing is "$L(M) \in \mathsf{P}?$". This is not the same as "does $M$ run in polynomial time?". For example $M$ could be the trial-division algorithm for deciding if the input is a prime number. This $M$ runs in exponential time but decides PRIMES, which is, famously, in P.
Sasho Nikolov
CC BY-SA 3.0
2015-02-22T06:41:40.793Z
Rice's theorem is applicable to the statement I made that immediately preceded it ('any property of an algorithm related to its output is undecidable') but is a bit of a non sequitur in relation to the rest of the post. I will edit to remove the confusion.
Joe Bebel
CC BY-SA 3.0
2015-05-08T02:04:54.907Z
Can you put a reference to the decidable examples you gave. Specifically the one with 500 steps? How do you prove this?
TheJKFever
CC BY-SA 3.0
2015-02-22T05:10:31.590Z
2015-02-22T07:04:42.357Z
2015-02-22T07:04:42.357Z
Joe Bebel
<p>In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding if a given algorithm runs in polynomial time, since the halting problem doesn't reduce to determining whether an algorithm is polynomial. So what research is there on it? Or what mistake am I making in my reasoning?</p>

CC BY-SA 3.0
2015-02-22T05:03:01.547Z
You can easily modify this reduction http://cstheory.stackexchange.com/a/5006/4896 to show that deciding if a Turing machine runs in $O(n^2)$ or $\Omega(f(n))$ time, for any $f(n) = \omega(n^2)$, is undecidable.
Sasho Nikolov
CC BY-SA 3.0
2015-02-22T09:34:43.063Z
This is not a research-level question. It is, as you say, undecidable whether an algorithm terminates for a specific input. So how could it be decidable whether an algorithm terminates for *all* inputs and always within polynomial time?
David Richerby
<ds.algorithms><time-complexity>
Algorithm to determine if given algorithm runs in polynomial time
Elliot Gorokhovsky
# Algorithm to determine if given algorithm runs in polynomial time

(Asked by: username_0 on 2015-02-22)

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding if a given algorithm runs in polynomial time, since the halting problem doesn't reduce to determining whether an algorithm is polynomial. So what research is there on it? Or what mistake am I making in my reasoning?

**Tags:** ds.algorithms, time-complexity

> **Comments:**
> **username_1**: You can easily modify this reduction http://cstheory.stackexchange.com/a/5006/4896 to show that deciding if a Turing machine runs in $O(n^2)$ or $\Omega(f(n))$ time, for any $f(n) = \omega(n^2)$, is undecidable.  
> **username_2**: This is not a research-level question. It is, as you say, undecidable whether an algorithm terminates for a specific input. So how could it be decidable whether an algorithm terminates for *all* inputs and always within polynomial time?  

---

## 1 answers

### Answer by username_3 on 2015-02-22. Score: 1 | Accepted answer

It might not be the Halting Problem exactly, but it is also not possible to decide if a given algorithm runs in polynomial time or not. The reason is the same as many other undecidable problems; using Kleene's Recursion theorem, an algorithm can always query if itself is a polynomial time algorithm, and can adopt the opposite behavior.

Example properties of algorithms that *are* decidable are things such as:

* If an algorithm's source code has less than 1000 characters
* If an algorithm, on a given input $x$, will halt within 500 steps
* If an algorithm's source code has a particular symbol in it

That is, properties of an algorithm that have nothing to do with its execution (or only a limited part of its execution) tend to be decidable, while any nontrivial property of a program's execution will likely be undecidable.

Also, in general, *any* property of an algorithm related to its output is undecidable (this is formalized by Rice's theorem), although running time is not a property of its output.

> **Comments:**
> **username_1**: I agree with you philosophically, but is Rice's theorem really applicable to the question? Rice's theorem, in the statement I am familiar with, talks about the decidability of the problem "Does the language decided by Turing machine $M$ have property $P$?". This does not capture questions about the running time of $M$.  
> **username_4**: @SashoNikolov: I think Rice's theorem does apply. The formal statement of Rice's theorem says that it's undecidable to determine whether the language a TM computes is in C for any non-trivial complexity class C. Here non-trivial means that there exists a TM deciding a language in C, and a TM deciding a language not in C. Clearly this holds when C = P.  
> **username_1**: @HuckBennett P is non-trivial but the problem you are describing is "$L(M) \in \mathsf{P}?$". This is not the same as "does $M$ run in polynomial time?". For example $M$ could be the trial-division algorithm for deciding if the input is a prime number. This $M$ runs in exponential time but decides PRIMES, which is, famously, in P.  
> **username_3**: Rice's theorem is applicable to the statement I made that immediately preceded it ('any property of an algorithm related to its output is undecidable') but is a bit of a non sequitur in relation to the rest of the post. I will edit to remove the confusion.  
> **username_5**: Can you put a reference to the decidable examples you gave. Specifically the one with 500 steps? How do you prove this?  

---

