In comp.theory Randy <firstname.lastname@example.org> wrote: > email@example.com wrote: >> In comp.theory Michael Hennebry <firstname.lastname@example.org> wrote: >> >>>An NP-hard decision problem need not be in NP, but it must be >>>decidable. >> >> >> I am not sure what the consensus on that is. According >> to some definitions I have seen the Halting Problem is NP-hard. >> If you could solve the Halting Problem in polynomial time, >> you could solve any problem in NP in polynomial time.
> I think any algorithm that contains uncertainty (indefinite input) can > still be assessed for time or space complexity. Whenever the problem > cannot be solved, its complexity must remain undefined. However, it > seems to me that when the problem can be solved, its complexity can be > characterized and maybe quantified.
Noone was talking about indefinite input. The Halting Problem is unsolvable and there is nothing indefinite or uncertain about the input.
> For example, a UTM that uses a small number of states will have a lower > time complexity than a UTM using (or that must explore) a larger number > of states.
That seems backwards for UTM. In general the number of states a TM has will have nothing to do with the complexity of its running time. I really doubt UTM's are an exception.