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 2:05 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

> But with luck, it'll help fill the gap between reality and theory...

> nimmi_srivastav@yahoo.com wrote:
>> 1) All the literature pertaining to intractability that I have seen
>> refers to the Turing's Halting Problem. What are other common examples
>> of intractable problems?


> Any task that is always solvable (decidable) and whose runtime grows
> exponentially with the size of its input set is NP Hard. In other
> words, if the input size of the task's data is N, the task's runtime is
> described by X^f(N), where X and f(N) are greater than 1 and are
> nondecreasing (they grow larger without ever growing smaller).


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

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

> The NPC problem lies within that subset of NP problems that
> we are certain they can never be solved in polynomial time, that is,
> unless it turns out that *ALL* problems in NP can be solved in
> polynomial time. Right now, it looks like P is smaller subset of
> problems that lie entirely within NP.


>> 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard
>> problem, does that have any implication for the P=NP question?
>> [I already know that if a polynomial time algorithm is discovered for a
>> hitherto NP-Complete problem, then P=NP]


> In general, yes. 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.

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

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

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

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.