
Re: On NP Completeness and Intractability
Posted:
Oct 25, 2005 5:49 PM


In comp.theory Randy <joe@burgershack.com> wrote: > stephen@nomail.com wrote: >> In sci.math Randy <joe@burgershack.com> wrote: >> >>>I'm not a theorist, so my terminology will probably be a bit imprecise. >> >> Unfortunately you are being very imprecise. Unfortunately this >> is an easy topic to be imprecise about, but one which >> you need to be precise about. You seem to be using a >> nonstandard definition of NPcomplete and NPhard >> and as a result most of your answers are incorrect according >> to the standard definitions.
> It's no surprise to me. IMHO, its because of its abstract terminology > (and the consequential confusion among nontheorists) that complexity > theory is almost entirely ignored by the professional CS community. > IMHO, this is because: 1) it's poorly explained by those who understand > it, and 2) it's deemed irrelevant by just about everyone, including many > who understand it better than I.
> IMHO, the latter is a shame, but the former is just shameful. It's > absurd that theorists (and mathematicians) are unwilling to explain the > concepts that lie beneath the jargon. But until they do, the rest of us > have to learn this stuff on our own and explain it in our own terms. > Ergo my imprecise explanation.
The terminology is pretty straightforward. The fact that you do not understand it is not evidence that there is something wrong with the terminology.
I apparently overestimated your understanding of the various terms, so my answers were not as precise as they could have been.
<snip>
>> >>>In other words, the problem's >>>runtime grows exponentially with size and 1) we know for sure that it >>>lies within the class of NP problems and 2) OUTSIDE the class of P >>>problems. >> >> >> No, we do not know that it is outside the class of P problems, >> nor do we know that the runtime is necessarily exponential.
> Are you aware of any exponential problems that are in P? I'm not, but > as you point out, I'm not expert.
Your comment is a nonsequiter. If a problem is NPcomplete, then it is not necessarily the case that its run time is exponential, or that is is outside of P. If P!=NP, then it is outside of P, but it is still not necessarily the case that is run time is exponential. There are run times between polynomial and exponential.
> Practitioners know perfectly well whether a given problem is effectively > exponential. Using L'Hopital's Rule, we can confirm that it grows > faster than polynomial. Does that make it exponential? For practical > purposes, I think it does. But for mathematicians, especially those who > seek to prove the theoretical equivalence of complexity classes, I > suppose it does not. Also, the OP sought an explanation "in lay terms". > As I said originally, I'm still trying to span that gulf.
> In fact, I've not seen a proof that NP Complete to NPHard reduction is > the *only* way to confirm that an NPHard problem is necessarily NPC.
That is the definiton of NPC.
> AFAIK, it's just the standard method. If an equivalent procedure were > available (which, in English, accomplishes *what* again?), other methods > for defining exponentiality or NP Completeness (which you imply as being > equivalent), would be equally purposeful.
> The point really is, "Why are NP Complete or NPHard important?" To the > lay person, I think it's not important as an end unto itself to prove NP > Hardness or NP Completeness. Reduction of a NPC problem to your problem > shows conclusively that your problem is polynomially as hard as other > NPC problems, and I suppose, that it resides in NP.
You suppose wrong. A reduction does not show that your problem is in NP. It does show that it is NPhard. If it is NPhard and is in NP, then it is NPcomplete.
> Thereafter, knowing > that, theorists can say something about the implications of solving that > problem in less than exponential time, and conversely, about the > likelihood of doing so. But I'm not sure the practitioner gains much.
What the practitioner gains from the theory of NPcompleteness is that there is a very large family of problems that people have studied for years and noone has ever found an efficient solution for any of them, and that if an efficient solution existed for any of them, an efficient solution would exist for all of them. So if you encounter a new problem, and you can demonstrate that it is NPcomplete, or NPhard, then it is highly doubtful that your are going to find an efficient solution to the problem. So your energies are better devoted to looking at approximation algorithms, heuristics, etc.
> Does that mean that the only way to show that a problem is exponential > is to prove that it's NP Complete? IMO, only a theorist would say yes.
I doubt any theorist would say that. Nobody knows if any NPcomplete problem requires exponential time or not.
> Which is important, the problem's exponentiality or the fact that it's > in NP? Until I observe problems that are exponential and NOT in NP, I > fail to see the practical nontheoretical value in differentiating > between NPC and NPHard.
And how do you propose to determine if a problem requires exponential time or not? You can write an algorithm, and collect data on its running time, but that only tells you something about that algorithm, and not much about the problem.
> [...] If a problem is NP Hard (exponential), then solving it >>>in polynomial time is a good sign that: 1) P=NP, or 2) the problem isn't >>>really exponential after all: either it's actually in P, or it's not as >>>hard as the hardest problems in NP: the NPCs. >> >> >> If a problem in NPhard then we know that it is as hard as the >> hardest problems in NP. That is the definition of NPhard. >> If you find a polynomial time solution for an NPhard problem >> then P=NP. There is no maybe about it.
> So there are NP Hard problems that are harder than NP Complete problems? > Harder than exponential, yet verifiable polynomially.
They are not verifiable polynomially. Problems in NP are verifiable in polynomial time. NPhard problems do not need to be in NP. You repeatedly make the assumption that NPhard problems must be in NP.
> Why is the > difference important, except as more or less infeasible? Or is the > value only theoretical?
The difference between NPhard and NPcomplete is probably not all that important for somebody designing algorithms. If you encounter a problem that is NPhard, then you are probably not going to find a polynomial time solution to the problem. If someone proves that P=NP, this is not going to necessarily help you with your NPhard problem. It may still not have a polynomial time solution. An NPcomplete problem will have a polynomial time solution if P=NP, but NPhard problems can be harder than that.
Stephen

