
Re: On NP Completeness and Intractability
Posted:
Oct 26, 2005 2:49 PM


In comp.theory Randy <joe@burgershack.com> wrote: > stephen@nomail.com wrote: >> In comp.theory Randy <joe@burgershack.com> wrote: > ... >>>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.
> The halting problem is entirely about what is known about: 1) the > program's input or 2) the program's search space. If there is no input, > or the input is completely known, or the search space is completely > known, then the program is deterministic and can be guaranteed to halt.
No. You are totally wrong. A deterministic algorithm is not guaranteed to halt.
> Halting is only undecidable when the input that is incompletely known > (e.g. infinite), or has an incompletely known effect on the program, as > in external instruction streams that might include or induce infinite > loops. Halting is also undecidable when the program's search space may > not include solutions that satisfy the program's given constraints and > is infinite, potentially causing the search to continue forever.
This is just nonsense. The halting problem is defined as follows: Given a program x and an input y, does x halt on y? x and y are both finite. There does not exist an algorithm that when given an x and y, always produces the correct answer. That is what it means for the problem to be unsolvable.
> Not being a mathematician, I can only guess that at its essence,
You should stop guessing and go read about this stuff.
Stephen

