Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
stephen@nomail.com

Posts: 1,744
Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 25, 2005 5:49 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


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 non-sequiter. If a problem is NP-complete,
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 NP-Hard reduction is
> the *only* way to confirm that an NP-Hard 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 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.


You suppose wrong. A reduction does not show that your problem
is in NP. It does show that it is NP-hard. If it is NP-hard
and is in NP, then it is NP-complete.

> 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 NP-completeness
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 NP-complete, or NP-hard,
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
NP-complete 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 non-theoretical value in differentiating
> between NPC and NP-Hard.


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


They are not verifiable polynomially. Problems in NP
are verifiable in polynomial time. NP-hard problems
do not need to be in NP. You repeatedly make the
assumption that NP-hard 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 NP-hard and NP-complete is probably not
all that important for somebody designing algorithms.
If you encounter a problem that is NP-hard, 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 NP-hard problem.
It may still not have a polynomial time solution. An NP-complete
problem will have a polynomial time solution if P=NP,
but NP-hard problems can be harder than that.

Stephen


Date Subject Author
10/25/05
Read On NP Completeness and Intractability
nimmi_srivastav@yahoo.com
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
ianparker2@gmail.com
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
osmium
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Ed Prochak
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
Gene
10/25/05
Read Re: On NP Completeness and Intractability
MartDowd
10/25/05
Read Re: On NP Completeness and Intractability
RobertSzefler
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
Wim Benthem
10/26/05
Read Re: On NP Completeness and Intractability
RobertSzefler
10/25/05
Read Re: On NP Completeness and Intractability
KP Bhat
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/25/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/25/05
Read Re: On NP Completeness and Intractability
nimmi_srivastav@yahoo.com
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
C6L1V@shaw.ca
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Wim Benthem
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Willem
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/27/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/28/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/28/05
Read Re: On NP Completeness and Intractability
Ben Rudiak-Gould
10/28/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/28/05
Read Re: On NP Completeness and Intractability
Pekka Orponen
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/25/05
Read Re: On NP Completeness and Intractability
Michael J. Hennebry
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/25/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/31/05
Read Re: On NP Completeness and Intractability
Oliver Wong
10/31/05
Read Re: On NP Completeness and Intractability
Robert Israel
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
Torkel Franzen
11/1/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
11/1/05
Read Re: On NP Completeness and Intractability
Oliver Wong
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
Robert Israel
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/26/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
Pat Farrell
10/25/05
Read On what "NP-Hard" means; was: Re: On NP Completeness and Intractability
Bryan Olson

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.