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 ]
 stephen@nomail.com Posts: 1,744 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 1:57 PM

In comp.theory Randy <joe@burgershack.com> wrote:
> Arthur J. O'Dwyer wrote:
>> On Wed, 26 Oct 2005, Randy wrote:
> [...]
>>
>> What on earth don't you understand? It seems like you came into the
>> discussion and said a lot of wrong things at once, and then everybody
>> else replied and said, "No, that's wrong, here's what's right." And
>> now you're saying that complexity analysis must be irrelevant to
>> (something; it's unclear what). No offense, but it's coming off as
>> "sour grapes."
>>
>> -Arthur

> OK. In lay terms (as the OP requested), why is NP meaningful to
> practitioners? What utilitarian subtlety does it capture that
> "exponential" does not?

That is not what the OP requested. He did not ask
anything about why NP is meaningful for practitioners.
He did ask for a description of the the difference between
NP-complete and NP-hard in "somewhat layterms".

and expontential is that you can actually prove that a problem is
NP-complete. If we could prove that any of the intractable problems
that we typically encounter actually required exponential time
then that would prove that P<>NP. On the other hand if someone proves
that P=NP, then all the problems you are apparently calling
"exponential" are in fact not exponential.

Just because the algorithm you use to solve a problem
requires exponential time it does not mean the problem
actually requires exponential time. There could be a
better algorithm that you have not thought of.
However if you know the problem is NP-complete, then
it is not just you, but thousands of people people working for
some 40+ years have also failed to find a better algorithm. That
is a useful thing to know and definitely has more weight
than just knowing that one person was unable to solve it.

I am sure lots of practitioners out there who really
do not care about NP-completeness, just as there
seem to be lots of engineers out there who really
do not care about math or physics other than the little
bits they need for their jobs. So what? Noone
says you have to care. There are lots of people
out there doing things that I do not care about,
but I do not see any reason to get upset about it.

Stephen

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