Randy
Posts:
19
Registered:
12/13/04


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


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.
... > >>>2) In somewhat layman terms, what exactly is the difference between >>>NPHard and NPComplete? > > >>In lay terms, there is no difference. Both describe problems whose >>solutions require runtimes that grow exponentially as their input data >>size grows linearly. "NP Complete" simply indicates that it's an "NP >>Hard" problem that has been translated into another NP Hard problem that >>is already known to be NP Complete. > > > No, NPComplete means that the problem is in NP and it is > NPhard. You can prove a problem is NPhard by reducing > it to another NPhard problem. There is no need to use > an NPcomplete problem to show that a problem is NPhard.
Of course. But saying that conveys no information to someone who is not a theorist who already understands all the subtleties of the terms P and NP, and the nuances among the conceptual hierarchy of problems having exponential runtimes.
Consider this example, an equally rigorous translation of what you said:
"FOO CONGEALED means that the problem is in FOO and it is FOOSLIPPERY. You can prove a problem is FOOSLIPPERY by SLIMEing it to another FOOSLIPPERY problem. There is no need to use an FOOCONGEALED problem to show that a problem is FOOSLIPPERY."
Not too helpful, is it?
In the end, if the OP is interested in learning more about CS theory, then they'll investigate further and if they try really hard, they'll fully comprehend the terminology you have used, as well as the flaws that lie in my hand waving. The challenge is, how can an interested party come to understand complexity theory when they don't already understand the terminology? Running circles around them logically just leaves them confused.
As you point out, I too am having some trouble appreciating where the conceptual lines are drawn. And I've read Garey and Johnson from cover to cover...
> >>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.
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. 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. 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.
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. 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.
[...] 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. Why is the difference important, except as more or less infeasible? Or is the value only theoretical?
> >>NP Complete just means that these are the hardest problems that we know >>that are always solvable. Solving any of these in polynomial time is a >>guarantee that all alwayssolvableproblems (all of NP) can be solved in >>polynomial time. > > > No, there are plenty of problems "harder" than NPcomplete problems > that are solvable, assuming of course that P!=NP. For example, > any NPhard problem that is not NPcomplete. Of course proving > that a problem is not NPcomplete is not trivial. I do not > recall if there are any NPhard problems that have been definitely > proven to not be NPcomplete.
Hmm. I understand that "ExpTime" is apparently such a class, (which I understand to be 2^(N^Z), where Z is a polynomial). But I wasn't aware that such problems could be verified by a DTM in polynomial time. If they ain't, then presumably they ain't in NP. Which makes them a horse of entirely another color...
The difference between exponentiality and uberexponentiality doesn't seem meaningful to me outside of CS theoretical proofs. I have to wonder whether there should be another class called ExpExpPoly, described by 2^(2^(N^Z)). But does this hair splitting not continue ad nauseum? Doesn't the fact that such problems fall outside NP imply a lot less relevance to those of us who do not live in castles built in the air?
I think NP Hard is interesting because it seems to me to define a useful landmark in identifying and comparing classes of algorithms that are basically infeasible. But the meaning of the distinction between NPC and NP Hard is lost on me, other than defining constraints that are necessary and sufficient for safely manipulating the concepts of the complexity hierarchy.
> >>Thus, until we prove that a given NP Hard problem is equally as hard as >>the hardest problem in NP, we can't be sure that solving it in >>polynomial time guarantees that we can solve all other solvable problems >>in polynomial time. > > > By definition an NPhard problem is as hard as the hardest > problem in NP. That is the definition of NP.
Or is that the definition of NPHard? I don't see the value of the definition of NP as an upper bound to exponential as compared to NPC. NPC seems to be only a formal definition of a polynomialdegree of equivalence among exponentially hard problems. To say that a problem is NPHard but not NPComplete seems to me not a useful distinction except to say that the NP Hard problem has not yet been shown to be reducible to a known NPC problem. AFAIK, both are exponential and both probably can be verified in polynomial time using a DTM.
NPHard seems to imply not that it's a costlier problem, but only that we have yet to formally reduce 3SAT (or its NPC brethren) to it.
I guess I need to see an example problem that's NP Hard and *cannot* be NPComplete.
> > <snip> > > As I said earlier, your definitions of NPcomplete and NPhard are > nonstandard, and as a result most of your answers are incorrect > according to the standard definitions.
OK. I'm not as precise as I should be with NPHard. But I'm still not appreciating the implications for the term, since it's not clear what it means outside of theory for a problem to be harder than NPComplete ("super exponential" means what?). Nor for the practical implications for being NPC vs NP Hard. Nor what it means to be decidable but not in NP. What sort of problem would that last case be, other than compound exponential that cannot be verified in polynomial time? In other words, the problem is worse than infeasible. It's hopeless?
Randy
> > Stephen
 Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

