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 ]
 KP Bhat Posts: 1 Registered: 10/25/05
Re: On NP Completeness and Intractability
Posted: Oct 25, 2005 6:06 PM

martin dowd wrote:
> Important examples of unsolvable problems include:
> -is a statement of predicate logic valid?
> -is a statement in the language of rings true in the theory of rings?
> -is a polynomial with integer coefficients have an integer root?
> The list goes on.
>
> NP hard means every problem is NP is no harder. NP complete means in
> addition the problem is in NP.
>

My \$0.02 worth...

The meaning of the word "hard" refers to time complexity. In order to
be NP-Hard, the time complexity should be worse than or equal to the
time complexity of a known problem in NP. It's as if we are saying
"As bad as NP". Furthermore, even though we make that comparison,
the problem itself may not even be in NP. We are using NP as just the
benchmark. That is why unsolvable problems like the Halting Problem
are considered NP-Hard (all we are saying is that it is as bad as any
NP problem out there). When a problem is NP-Hard and it itself is in
NP, then it is called NP-Complete.

Cook (the gentleman who opened this whole can of worms in 1971)
conjectured something to this effect:

"If the satisfiability problem can be solved in polynomial time, a
non-deterministic Turing Machine will be no more powerful than a
deterministic Turning machine. In other words, non-determinism alone
will not help in solving any problem".

In course of time, people reduced other problems to the satisfiability
problem (i.e the set of NP Complete problems expanded rapidly),
effectively saying that if a polynomial algorithm can be found for any
one of these problems, then P=NP. By the same token, if it can be
proven that no polynomial algorithm for any one of these problems, P !=
NP

Having said that, can someone come up with more problems that are
NP-Hard ---- BUT NOT ------ NP Complete? Dowd's list above is a good
starting point. My guess is that only a handful of problems fall into
this category.

Is that correct?

IMHO an overwhelming majority of NP-Hard problems are also NP-Complete.

Thanks,
Bhat

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