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 ]
 Michael J. Hennebry Posts: 132 Registered: 12/11/04
Re: On NP Completeness and Intractability
Posted: Oct 25, 2005 4:12 PM

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?
> 2) In somewhat layman terms, what exactly is the difference between
> NP-Hard and NP-Complete?
> 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]
> 4) When we refer to NP, without any qualifiers, does it imply NP-Hard?

The Halting problem is undecidable.
The means that there is no algorithm that will solve it.

The P of decision problem classes P, NP, and co-NP
refers to polynomial time.

A decision problem, e.g., does integer X divide integer Y,
is in P iff it can be solved in polynomial time.

A decision problem, e.g. is X composite, is in NP iff for
in polynomial time with a lucky guess, e.g a factor of X.

A decision problem, e.g. is X prime, is in co-NP iff
its opposite, e.g. is X composite or 1, is in NP.

NP-complete and NP-hard are usually used as adjectives, e.g.
SAT is NP-complete.
The class of NP-complete problems is sometimes called NPC.
I've never seen NPH.

A problem is NP-complete iff any problem in NP can be converted
to it in polynomial time.
That is the mechanism by which finding a polynomial algorithm
for NPC would allow solving all of NP and co-NP in polynomial time.

An NP-hard problem is at least as hard as every problem in NP.
Another poster said that an NP-hard problem need not be a decision
problem.
An NP-hard decision problem need not be in NP, but it must be
decidable.

There are other classifications of decision problems.
E.g. PSPACE is the class of decision problems whose
solution requires a only polynomial amount of memory.
It includes decidable problems that are in neither NP
nor co-NP.

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