
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 NPcomplete and NPhard in "somewhat layterms".
To answer your question, the difference between NPcomplete and expontential is that you can actually prove that a problem is NPcomplete. 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 NPcomplete, 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 NPcompleteness, 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

