firstname.lastname@example.org wrote: > In comp.theory Michael Hennebry <email@example.com> 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.
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.
> > It does not make much sense to talk about the complexity > of an undecidable problem, and in discussions of complexity > undecidable problems are usually ignored, but > technically they do fit the definitions of some of the > complexity classes.
I think this is a comparable topic to past attempts within AI to manage the time costs of various computational or search methods. When a problem's search space is infinite, or uncertainty overwhelms certainty, or noise hides signal, these situations are comparable to undecidability. But I don't think they're entirely unmanageable.