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