NP-np hard和np complete-Complete的区别

algorithm - NP-Complete VS NP-Hard - Stack Overflow
Join the Stack Overflow Community
Stack Overflow is a community of 7.0 million programmers, just like you, helping each other.
J it only takes a minute:
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?
2,840111631
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.
1,46711222
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.
1,19911223
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
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
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 (i.e. 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!
2,840111631
Your definition is only correct for NP-complete.
Starting from the bottom: P is the class of problems that can be solved by some deterministic Turing machine in polynomial time. NP is the class of problems that can be solved by some non-deterministic Turing machine in polynomial time (or whose solutions can be verified by deterministic Turing machines in polynomial time).
As for NP-hard, it means decision problems X that have the following property: given a Turing machine that solves the problem, one could restructure (Turing reduction) any instance of a problem in NP to an instance of X in polynomial time. Informally, this means that NP-hard problems are those that are "at least as hard as NP", or that the solution for X could be applied to every problem in NP. Note that the problem doesn't have to be verifiable in polynomial time, or actually verifiable at all. NP-hard includes undecidable and unrecognizable problems as well.
We don't know if NP-hard includes problems that can be solved in polynomial time or not (the P ?= NP problem). Currently, not a single polynomial-time solution for a NP-hard problem has been found, but neither has it been proven that such solution can't exist. If such a solution was found for some NP-hard problem X, that would mean P = NP as any instance of any problem in NP could be converted to an instance of X in polynomial time (because of the Turing reduction property of NP-hard problems) and then be solved in polynomial time by X's polynomial time solution.
2,71211327
Let me make it simple.
A professor gives his students a problem, and asks them to provide an efficient algorithm.
Next day, some of his intelligent students have cracked the algorithm to solve it. It has a complexity of O(2n). Now, all are happy that they have got the algorithm to get the solution. Everything looks good.
The professor appreciates them, but says, "The task is not yet over", and challenges them to solve it practically using a system.
So, they immediately try to emulate it in the system. A student says, his system has a fantastic speed
of 1 GIPS ( instructions per second) and that it can solve the problem within fractions of a second. So, they code their algorithm and try to execute it.
Then they start with 100 inputs to the data set, and they run it. They were surprised to see that the program runs and runs and runs and doesn't come to a halt.
Then another student did a math on it and figured out that, the system would
take 2100 / 109 seconds to solve it. Roughly around 240 years.
Next day, while the program was still running, the professor said, "Very well. My dear students, this is what we call NP-Hard. The system might give the solution one day, but I'm afraid we won't be there to see it".
But, the same problem, once it generates a solution, if we are able to verify the solution of a NP-Hard problem in realistic time, then it's called NP-Complete. For example, Sum of Subsets is a NP-Hard problem. But, once we get a subset solution, we can check it easily in polynomial time. So it becomes NP-Complete.
Your Answer
Sign up or
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Post as a guest
By posting your answer, you agree to the
Not the answer you're looking for?
Browse other questions tagged
rev .25642
Stack Overflow works best with JavaScript enabled酷勤网 C 程序员的那点事!
当前位置: >
浏览次数:次
很多人一看到NP-hard,就从字面上理解成为比NP还难的问题。但如果这里的&更难&指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看,NP-hard问题的确比NP难,但比NP还难(指花费时间更多)的问题却不见得是NP-hard的。
仔细检查NP-hard的定义:一个问题(语言)L是NP-Hard的,当且仅当3SAT问题可以在多项式时间规约到L,即存在一个可多项式时间计算函数f,使得当且仅当。
注意NP-hard的概念只有在NP!=P的时候才有意义,因为在NP=P的时候,除了空集和全集语言外,所有问题都是NP-hard的。
但在NP!=P的时候,NP-hard问题的分布呈什么状态呢?
定理1:所有unary语言都不可能是NP-hard的(除非NP=P)。语言L是unary的,指L里的任一元素都是1n的形式。
根据此定理,如果我们能找到一个NP-hard的unary的undecidable问题,就证明NP=P了& 。
定理2:Turing机停机问题是NP-hard(by Dr. Sun)。
这个定理有点出人意料,但仔细想想也不难证明。而且这个问题不难转成unary的形式,可惜这个转化过程不是多项式时间的,所以转化过后就不一定是NP-hard的了。
思考1:NEXP里有问题不是NP-Hard吗?
思考2:为什么NP-complete用多项式时间规约,PSPACE-complete也用多项式时间归约,而不是多项式空间规约?
& 相关主题:}

我要回帖

更多关于 np hard问题举例 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信