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

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

In sci.math 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?



The Halting Problem is an undecidable problem. That means
that there does not exist an algorithm that correctly solves
it. The word "intractable" is usually used to describe
problems that can be solved, but cannot be solved efficiently.
For example, the Travelling Salesman problem can be solved
by trying all possible tours and taking the mininum. However
this is a very inefficient algorithm and is essentially useless
for more than a small number of cities.

> 2) In somewhat layman terms, what exactly is the difference between
> NP-Hard and NP-Complete?


A problem is NP-Hard if it is at least as hard as any problem
in NP. A problem is NP-Complete if it is NP-Hard and it is
in 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]


A polynomial time solution for an NP-Hard problem implies P=NP.
The fact that NP-Complete problems are NP-Hard is why a polynomial
time solution for an NP-complete implies P=NP.

> 4) When we refer to NP, without any qualifiers, does it imply NP-Hard?

No. NP just means that it can be solve in non-deterministic
polynomial time. Remember, NP includes all the decision
problems that are in P.

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.