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 ]
 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
> 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."

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?

Randy

>
> Stephen

--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

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