Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

 Messages: [ Previous | Next ]
 Randy Posts: 19 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 26, 2005 2:32 PM

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.

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.

Not being a mathematician, I can only guess that at its essence, the
halting problem could be regarded as a function that fails because 1)
its domain is incompletely known or 2) its range is incompletely known.
If that simplification is fair, then undecidability is inextricably
linked to incomplete knowledge, ergo uncertainty.

This is where others who have explored the boundary between certainty
and uncertainty come in (in my example, a few AI folks). In practice,
it is possible to manage a program's inability to halt or its
potentially infinite search, just in the way that Operating Systems
detect deadlocks and kill nonresponsive processes that are stuck in
infinite loops. Just as in probabilistic algorithms, the criterion for
"halt" is redefined no longer to be "optimal", but "close enough". Such
algorithms will then have measurable asymptotic complexity measures.

Yes, the imposed limits on the algorithm artificially reshape its
complexity. But so what? Just pretend the core algorithm and its
keeper are one, and voila, you've built a compound program that 1) halts
and 2) has a complexity measure.

For fun, to confirm that input is not central to the halting problem,
try removing the word "input" from the Wiki entry:

http://en.wikipedia.org/wiki/Halting_problem

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

My point is that the size of the problem's input space or search space
or even the UTM's execution space will dictate the effective runtime.
It the UTM is based on a quantum computer or a CA, which must explore
more states than another UTM to get the same job done, perhaps even
nondeterministically, then the speed of the machine will matter too.

Randy

--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

Date Subject Author
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 Dr. David Kirkby
10/25/05 ianparker2@gmail.com
10/25/05 Pubkeybreaker
10/25/05 osmium
10/25/05 Pubkeybreaker
10/25/05 Willem
10/25/05 Bryan Olson
10/25/05 Willem
10/25/05 Ed Prochak
10/25/05 Dr. David Kirkby
10/25/05 Gene
10/25/05 MartDowd
10/25/05 RobertSzefler
10/25/05 Dr. David Kirkby
10/25/05 Pubkeybreaker
10/25/05 Wim Benthem
10/26/05 RobertSzefler
10/25/05 KP Bhat
10/25/05 stephen@nomail.com
10/25/05 tchow@lsa.umich.edu
10/25/05 googmeister@gmail.com
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/27/05 stephen@nomail.com
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 C6L1V@shaw.ca
10/25/05 stephen@nomail.com
10/25/05 Wim Benthem
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/26/05 Randy
10/27/05 Arthur J. O'Dwyer
10/27/05 Randy
10/27/05 Willem
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 tchow@lsa.umich.edu
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Arthur J. O'Dwyer
10/27/05 googmeister@gmail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 Arthur J. O'Dwyer
10/28/05 Joe Hendrix
10/28/05 Ben Rudiak-Gould
10/28/05 Bryan Olson
10/28/05 Pekka Orponen
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/25/05 tchow@lsa.umich.edu
10/25/05 Michael J. Hennebry
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/25/05 Willem
10/25/05 Arthur J. O'Dwyer
10/25/05 googmeister@gmail.com
10/31/05 Oliver Wong
10/31/05 Robert Israel
11/1/05 Willem
11/1/05 googmeister@gmail.com
11/1/05 Willem
11/1/05 Torkel Franzen
11/1/05 googmeister@gmail.com
11/1/05 Oliver Wong
11/1/05 Willem
11/1/05 Robert Israel
10/26/05 Randy
10/26/05 stephen@nomail.com
10/26/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/25/05 Pat Farrell
10/25/05 Bryan Olson