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 NPHard, 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 NPHard (all we are saying is that it is as bad as any NP problem out there). When a problem is NPHard and it itself is in NP, then it is called NPComplete.
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 nondeterministic Turing Machine will be no more powerful than a deterministic Turning machine. In other words, nondeterminism 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 NPHard  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 NPHard problems are also NPComplete.
Thanks, Bhat

