Complete VS NP
I am trying to understand the difference between NP-Complete and NP-Hard.
Below is my understanding
An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time.
An NP-Complete problem is one that is in NP and is also NP-Hard.
Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?
A NP problem (not NP-Hard problem) is a decision problem which can be verified in polynomial time. Maybe they are solvable in polynomial time, since all problems in P are also in NP .
A NP-complete problem is a decision problem , which all NP problems can reduced to in polynomial time. They are the hardest problems in the class NP .
The NP-hard class is the class of the problems which are at least as hard as the NP-complete problem. They are not necessarily a decision problem. Given that we don't know whether NP = P or not, it would be hard to say whether we can verify a NP-hard problem in polynomial time.
For example, the decision problem of maximum clique (Give a graph G an integer K , to tell whether there is a complete graph with at least K vertices ) is NP problem. It is also NP-complete and NP-hard . However, maximum clique problem (Find the maximum clique in the given Graph) is not NP or NP-complete , since it is not decision problem. We can say it is NP-hard , since it is at least as hard as the decision version of maximum clique problem.
NP-Hard is lower bound on the problem. Impossible problems are also NP-Hard. NP-Complete means that it is NP-Hard and at the same time NP-Solvable.
Problems that can be verified in polynomial time is one of the definitions of problems in NP.
Your definition for NP-Hard is not correct, it looks more like the (not precisely correct) definition of the complexity class NP.
What is the complexity class NP?
A computational problem p is in the complexity class NP if it can be efficiently verified. In complexity theory, we deem computation that takes polynomial time to be efficient. So formally p ∈ NP if p is polynomial-time verifiable.
In your definition, you mentioned the concept polynomial-time solvable, which corresponds to the complexity class P. A NP-Complete problem is polynomial-time solvable if and only if P = NP. Note that the famous P vs NP is one of the biggest open problems in Computer Science, so currently no one knows whether P = NP or P ⊊ NP, and it is inappropriate to say that NP problems are not polynomial-time solvable (though it is widely believed to be the case).
What are NP-Hard problems?
Intuitively, NP-Hard problems are computational problems that are at least as hard as the problems in NP. When we say a computational problem p is at least as hard as another problem q , we actually think about it reversely - if we can solve p in time T, than we can also solve q in time roughly the same as T (say, differ by a polynomial factor).
More precisely, we say that p is at least as hard as another problem q if there is a polynomial-time reduction from q to p . Roughly speaking, a polynomial-time reduction means given an algorithm A that solves p , we can construct a polynomial-time algorithm B by using A as black-box (ie we treat the time complexity of A as O(1) ) to solve q .
In our case of NP-Hard problem, if an NP-Hard problem can be solved in polynomial-time, then ALL NP problems can be solved in polynomial-time (and hence P = NP!). So it is widely believed that NP-hard problems are NOT polynomial-time solvable.
What are NP-Complete problems?
As you have stated correctly in your question, a computational problem p is NP-Complete if it is NP-Hard and p ∈ NP .
NP-Hard problems that are not in NP?
If there exists a NP-Hard problem that is not in NP (to the best of my knowledge, no such problem has been proved to fall in this category at this moment of time), such problem is harder than NP-Complete problems.
Proof: Suppose our claim is not true. Let p be a NP-Complete problem that is at least as hard as another problem q that is NP-Hard but not in NP. Since p is at least as hard as q , we have a polynomial-time reduction (say it runs in time P(n) ) from q to p . Since p is in NP, it can be verified by some algorithm A in time T(n) where T is a polynomial.
Now given any instance r of q , we can construct an algorithm B by first reduction it to an instance s of p , and then invoke A to verify s . Note that B verifies q in time T(P(n)) , which is a polynomial in n , it follows that q is in NP, which gives us a contradiction!
上一篇: 关于P的一些澄清
下一篇: 完整VS NP