firstname.lastname@example.org wrote: > In sci.math Randy <email@example.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 > non-standard definition of NP-complete and NP-hard > 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 non-theorists) 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 >>>NP-Hard and NP-Complete? > > >>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, NP-Complete means that the problem is in NP and it is > NP-hard. You can prove a problem is NP-hard by reducing > it to another NP-hard problem. There is no need to use > an NP-complete problem to show that a problem is NP-hard.
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 FOO-SLIPPERY. You can prove a problem is FOO-SLIPPERY by SLIME-ing it to another FOO-SLIPPERY problem. There is no need to use an FOO-CONGEALED problem to show that a problem is FOO-SLIPPERY."
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 NP-Hard reduction is the *only* way to confirm that an NP-Hard 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 NP-Hard 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 non-theoretical value in differentiating between NPC and NP-Hard.
[...] 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 NP-hard then we know that it is as hard as the > hardest problems in NP. That is the definition of NP-hard. > If you find a polynomial time solution for an NP-hard 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 always-solvable-problems (all of NP) can be solved in >>polynomial time. > > > No, there are plenty of problems "harder" than NP-complete problems > that are solvable, assuming of course that P!=NP. For example, > any NP-hard problem that is not NP-complete. Of course proving > that a problem is not NP-complete is not trivial. I do not > recall if there are any NP-hard problems that have been definitely > proven to not be NP-complete.
Hmm. I understand that "Exp-Time" 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 uber-exponentiality doesn't seem meaningful to me outside of CS theoretical proofs. I have to wonder whether there should be another class called Exp-Exp-Poly, 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 NP-hard problem is as hard as the hardest > problem in NP. That is the definition of NP.
Or is that the definition of NP-Hard? 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 polynomial-degree of equivalence among exponentially hard problems. To say that a problem is NP-Hard but not NP-Complete 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.
NP-Hard seems to imply not that it's a costlier problem, but only that we have yet to formally reduce 3-SAT (or its NPC brethren) to it.
I guess I need to see an example problem that's NP Hard and *cannot* be NP-Complete.
> > <snip> > > As I said earlier, your definitions of NP-complete and NP-hard are > non-standard, 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 NP-Hard. 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 NP-Complete ("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?