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 27, 2005 4:37 PM

Joe Hendrix wrote:
> Randy wrote:
...
>
> This suggests you still don't understand what NP complete and NP hard
> mean. Algorithms are not NP complete, problems are. Algorithms may
> have a polynomial time running time, an exponential time, or something
> even worse. A good algorithm doesn't even have to always terminate to
> be useful -- Knuth-Bendix completion is a good example of an important
> algorithm that does not.

Is the issue here one of solution space vs problem space, algorithm vs
problem description, thereby necessitating and justifying the need for
dissimilar KINDS of complexity? If so, that explains a lot. In
essence, CC exists because it's meaningless to equate complexity
measures in the problem and solution space. Which is what I've been
doing, unsuccessfully.

...
>
> Well, I am not in theory and find NP completeness useful. I don't know
> what you mean by informal algorithmists though. A computer science
> algorithm is by definition a formal entity. How do you expect a machine
> to execute an informal algorithm? In my experience in automated reasoning,
> NP completeness is a good result to achieve, since it suggests that
> techniques like SAT solving or linear arithmetic decision procedures may
> be able to efficiently solve problems in practice. Higher complexity
> classes usually require more exhaustive search.

I won't dispute that finding a problem to be NPC has value. But simply
quantifying its theta asymptotic complexity would seem to be equally
valuable, seemingly more so, and without the added burden of proving
that the problem's in NP.

Or am I still confusing apples (problems) with oranges (solutions)?

In other words, isn't proving NPC overkill if all you want to do is
characterize a problem? Wouldn't it be equally effective to identify a
problem's worst case runtime and then choose among known techniques that
efficiently solve problems with equal worst case (or theta) complexity?
CC's departure from traditional complexity analysis doesn't seem like
it adds that much value, especially in "the real world" where theta's
constants and exponents really do matter.

>
> This discussion might make since if you were talking about some exotic
> class perhaps involving machines with oracles, but NP completeness is a
> very basic concept.

OK, presuming that the goal of CC is NOT to assess problems rather than
solutions, the value of showing membership in NP as opposed to just
identifying worst case complexity is something that still don't
appreciate. If so, I'll willingly admit that the failure is mine.

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