NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. – Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.
This means that the problem can be solved in Polynomial time using a Non-deterministic Turing machine (like a regular Turing machine but also including a non-deterministic "choice" function). Basically, a solution has to be testable in poly time. If that's the case, and a known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete.
The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time.
Edit: As others have noted, there are often approximate solutions for NP-Complete problems. In this case, the approximate solution usually gives an approximation bound using special notation which tells us how close the approximation is.
NP Hard：指多项式时间尚未找到解决方案，但肯定无法在多项式时间中得到验证。 NP Hard 问题超越 NPC 难度。
Basically this world's problems can be categorized as
1) Unsolvable Problem 2) Intractable Problem 3) NP-Problem 4) P-Problem
1)The first one is no solution to the problem. 2)The second is the need exponential time (that is O (2 ^ n) above). 3)The third is called the NP. 4)The fourth is easy problem.
P: refers to a solution of the problem of Polynomial Time.
NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.
NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.
NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
There is polynomial-time proof for every instance of the problem with a "yes" answer that the answer is "yes", or (equivalently)
There exists a polynomial-time algorithm (possibly using random variables) that has a non-zero probability of answering "yes" if the answer to an instance of the problem is "yes" and will say "no" 100% of the time if the answer is "no." In other words, the algorithm must have a false-negative rate less than 100% and no false positives.
A problem X is NP-Complete if
X is in NP, and
For any problem Y in NP, there is a "reduction" from Y to X: a polynomial-time algorithm that transforms any instance of Y into an instance of X such that the answer to the Y-instance is "yes" if and only if the answer X-instance is "yes".
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
The class P consists of those problems that are solvable in polynomial time. For example, they could be solved in O(nk) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.
The class NP consists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.
Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.
NP-Complete means the problem is at least as hard as any problem in NP.
It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.
Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
(a or b) and (b or !c) and (d or !e or f) ...
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
了解我们正在尝试解决的问题而不是我们用来解决问题的算法会很有帮助。 所以我们会说所有具有良好扩展算法的问题都“在 P 中”。 那些具有较差扩展性的算法是“NP”。
这意味着许多简单的问题也是“NP”问题，因为我们可以编写糟糕的算法来解决简单的问题。 知道 NP 中的哪些问题是真正棘手的问题固然很好，但我们不仅仅是想说“这是我们还没有找到好的算法的问题”。 毕竟，我可以提出一个我认为需要超级惊人算法的问题（称之为 X）。 我告诉全世界，我能想出的解决 X 的最佳算法规模很糟糕，所以我认为 X 是一个非常棘手的问题。 但是明天，也许比我聪明的人发明了一种算法，可以解决 X 并且在 P 中。所以这不是一个很好的难题定义。
尽管如此，NP 中有很多问题没有人知道一个好的算法。 因此，如果我能够证明 X 是某种类型的问题：解决 X 的良好算法也可以以某种迂回的方式使用，以给出一个好的算法NP 中所有其他问题的算法。 现在人们可能更加确信 X 是一个真正棘手的问题。 在这种情况下，我们称 X 为 NP-Complete。
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
I have heard an explanation, that is:" NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the NP complexity class is that problems within that class can be verified by a polynomial time algorithm. As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.
A problem is classified as NP-complete if it can be shown that it is both NP-Hard and verifiable in polynomial time. Without going too deeply into the discussion of NP-Hard, suffice it to say that there are certain problems to which polynomial time solutions have not been found. That is, it takes something like n! (n factorial) steps to solve them. However, if you're given a solution to an NP-Complete problem, you can verify it in polynomial time.
A classic example of an NP-Complete problem is The Traveling Salesman Problem."
P is the set of problems which could be solved in polynomial time with a deterministic TM.
NP is the set of problems which requires a non-deterministic TM to be solved in polynomial time. This means that we can check all different combinations of variables in parallel with each instance taking polynomial time. If the problem is solvable then at least one of those parallel instances of TM would halt with "yes". This also means that if you could make a correct guess about the variables/solution then you just need to check it's validity in polynomial time.
NP-Hard is the set where problems are harder than NP. This means NP-Hard problem are more difficult than any problem in NP set. These problems are exponential even when using non-determinism of Turing machines. So parallel computation does not helps while solving these problems.
NP-Complete is the intersection set of NP and NP-Hard. According to what I understood,
problems in NP-Complete are at least as hard as the hardest problem in the NP set.
The class of all NP-Complete problems are equivalent to each other, i.e, a problem in NP-Complete set can be reduced to any other NP-Complete problem. That means if any of the NP-Complete problem would have an efficient solution then all of the NP-Complete problems could be solved with same solution.
If any problem in NP-Complete set is deterministically solvable in polynomial time, then the entire NP-Complete set is deterministically solvable in polynomial time. Also since NP-Complete problems are at least as hard as the hardest problem in the NP set, all problems in the NP set (which are equal or easier than the problems in NP-Complete set) will be bounded above by deterministically polynomial running time, expanding the P set over the NP set, resulting in P=NP.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.
发布评论
评论（14）
NP问题：-
Np 问题的类型
NP 完全问题：-
1 决策问题 A 称为 NP 完全，如果它具有以下两个属性：-
一些例子：
NP Problem :-
Type of Np Problem
NP Complete problem :-
1 Decision Problem A is called NP complete if it has following two properties:-
Some Ex :-
NP 完全问题是一组问题，其中每个问题
其他 NP 问题可以在多项式时间内减少，其解决方案
仍然可以在多项式时间内验证。 也就是说，任何NP问题都可以表示为
转化为任何 NP 完全问题。
– 非正式地，NP 完全问题是至少同样“困难”的 NP 问题
与 NP 中的任何其他问题一样。
NP-complete problems are a set of problems to each of which any
other NP-problem can be reduced in polynomial time, and whose solution
may still be verified in polynomial time. That is, any NP problem can be
transformed into any of the NP-complete problems.
– Informally, an NP-complete problem is an NP problem that is at least as "tough"
as any other problem in NP.
什么是 NP？
NP 是所有决策问题（带有是或否答案的问题）的集合，其中“是”答案可以在多项式时间 (O(nk) 内验证，其中 n 是问题大小，k 是一个常数）由确定性图灵机 。 多项式时间有时用作快或很快的定义。
P 是什么？
P 是确定性图灵机可以在多项式时间内解决的所有决策问题的集合。 由于它们可以在多项式时间内求解，因此也可以在多项式时间内验证它们。 因此P是NP的子集。
什么是NP-Complete？
当且仅当 NP 中的所有其他问题都可以快速（即在多项式时间内）转换为 x 时，NP 中的问题 x 也是 NP 完全的。
换句话说：
那么，NP-Complete 如此有趣的是，如果要快速解决任何一个 NP-Complete 问题，那么所有NP问题可以很快得到解决。
另请参阅帖子 什么是“P=NP？”，为什么这是一个如此著名的问题？
什么是NP-Hard？
NP-Hard 是至少与 NP 中最难的问题一样难的问题。 请注意，NP 完全问题也是 NP 困难问题。 然而，尽管有
NP作为前缀，但并非所有 NP 难题都是 NP（甚至是决策问题）。 也就是说NP-hard中的NP并不意味着非确定性多项式时间。 是的，这很令人困惑，但它的用法是根深蒂固的，不太可能改变。What is NP?
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
What is P?
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
What is NP-Complete?
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
In other words:
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
See also the post What's "P=NP?", and why is it such a famous question?
What is NP-Hard?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having
NPas a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.NP 代表非确定性多项式时间。
这意味着可以使用非确定性图灵机在多项式时间内解决问题（类似于常规图灵机，但也包括非确定性“选择”函数）。 基本上，解决方案必须在多次时间内可测试。 如果是这种情况，并且已知的 NP 问题可以使用给定的问题和修改后的输入来解决（NP 问题可以简化为给定的问题），那么该问题就是 NP 完全问题。
NP 完全问题的主要特点是它无法以任何已知的方式在多项式时间内求解。 NP-Hard/NP-Complete 是一种表明某些类别的问题在现实时间内无法解决的方法。
编辑：正如其他人所指出的，NP 完全问题通常有近似解决方案。 在这种情况下，近似解通常使用特殊符号给出近似界限，告诉我们近似值有多接近。
NP stands for Non-deterministic Polynomial time.
This means that the problem can be solved in Polynomial time using a Non-deterministic Turing machine (like a regular Turing machine but also including a non-deterministic "choice" function). Basically, a solution has to be testable in poly time. If that's the case, and a known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete.
The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time.
Edit: As others have noted, there are often approximate solutions for NP-Complete problems. In this case, the approximate solution usually gives an approximation bound using special notation which tells us how close the approximation is.
基本上这个世界的问题可以归类为
1）无法解决的问题
2）棘手的问题
3) NP问题
4) P-问题
1）第一个是没有解决问题的。
2）第二个是需要指数时间（即上面的O(2^n)）。
3）第三个称为NP。
4）第四个是简单的问题。
P：指多项式时间问题的解。
NP：指尚未找到解决方案的多项式时间。 我们不确定是否存在多项式时间解，但是一旦您提供解，该解就可以在多项式时间中得到验证。
NP Complete：指在多项式时间内我们还没有找到解决方案，但可以在多项式时间内验证。 NP问题中的NPC问题是比较困难的问题，因此如果我们能够证明我们有NPC问题的P解，那么可以在P解中找到NP问题。
NP Hard：指多项式时间尚未找到解决方案，但肯定无法在多项式时间中得到验证。 NP Hard 问题超越 NPC 难度。
Basically this world's problems can be categorized as
1) Unsolvable Problem
2) Intractable Problem
3) NP-Problem
4) P-Problem
1)The first one is no solution to the problem.
2)The second is the need exponential time (that is O (2 ^ n) above).
3)The third is called the NP.
4)The fourth is easy problem.
P: refers to a solution of the problem of Polynomial Time.
NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.
NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.
NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.
NP-Complete 意味着非常具体的东西，你必须小心，否则你会得到错误的定义。 首先，NP 问题是一个是/否问题，对于
问题 X 是 NP 完全的
如果 X 是 NP 完全的，并且存在确定性多项式时间算法，可以正确解决 X 的所有实例（0% 假阳性，0% 假阴性），则 NP 中的任何问题都可以用确定性多项式解决时间（减少到X）。
到目前为止，没有人提出这样一种确定性多项式时间算法，但没有人证明这种算法不存在（任何能做到其中之一的人都可以获得一百万美元：这是 P = NP 问题）。 这并不意味着您无法解决 NP 完全（或 NP 困难）问题的特定实例。 这只是意味着您无法拥有能够可靠地解决问题的所有实例的东西，就像您可以可靠地对整数列表进行排序一样。 您很可能能够想出一种算法，该算法可以很好地解决 NP-Hard 问题的所有实际实例。
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
A problem X is NP-Complete if
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
NP完全问题是一类问题。
P类包含可在多项式时间内解决的问题。 例如，对于某个常数 k，它们可以在 O(nk) 中求解，其中 n 是输入的大小。 简而言之，您可以编写一个在合理时间内运行的程序。NP类包含在多项式时间内可验证的问题。 也就是说，如果给我们一个潜在的解决方案，那么我们可以检查给定的解决方案在多项式时间内是否正确。一些例子是布尔可满足性（或 SAT）问题或哈密顿循环问题。 有许多已知问题属于 NP 类。
NP-Complete表示该问题至少与 NP 中的任何问题一样困难。它对计算机科学很重要，因为已经证明任何 NP 问题都可以转化为另一个 NP 完全问题。 这意味着任何一个 NP 完全问题的解决方案都是所有 NP 问题的解决方案。
安全领域的许多算法都依赖于这样一个事实：NP 难题不存在已知的解决方案。 如果找到解决方案，肯定会对计算产生重大影响。
NP-Complete is a class of problems.
The class
Pconsists of those problems that are solvable in polynomial time. For example, they could be solved in O(nk) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.The class
NPconsists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.
NP-Completemeans the problem is at least as hard as any problem in NP.It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.
Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
对于一类问题，我们必须模拟每种可能性以确保获得最佳解决方案。
对于一些 NP 完全问题，有很多好的启发式方法，但它们充其量只是一种有根据的猜测。
It's a class of problems where we must simulate every possibility to be sure we have the optimal solution.
There are a lot of good heuristics for some NP-Complete problems, but they are only an educated guess at best.
如果您正在寻找 NP 完全问题的示例，那么我建议您看一下 3-SAT 。
基本前提是你有一个 联合范式 的表达式，这是一种表示你有由 OR 连接的一系列表达式，所有表达式都必须为真：
3-SAT 问题是找到一个满足表达式的解决方案，其中每个 OR 表达式恰好有 3 个布尔值要匹配：
该解决方案可能是 ( a=T，b=T，c=F，d=F）。 然而，还没有发现任何算法可以在一般情况下在多项式时间内解决这个问题。 这意味着解决这个问题的最佳方法是进行简单的猜测和检查，并尝试不同的组合，直到找到有效的组合。
3-SAT 问题的特别之处在于任何 NP 完全问题都可以简化为 3-SAT 问题。 这意味着，如果您能找到多项式时间算法来解决此问题，那么您将获得 1,000,000 美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
老实说，维基百科可能是寻找此问题答案的最佳场所。
如果 NP = P，那么我们可以比我们之前想象的更快地解决非常困难的问题。 如果我们在 P（多项式）时间内仅解决一个 NP 完全问题，那么它可以应用于 NP 完全类别中的所有其他问题。
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
我们需要将算法和问题分开。 我们编写算法来解决问题，并且它们以某种方式扩展。 尽管这是一种简化，但如果缩放足够好，我们就用“P”标记算法，如果不够好，则用“NP”标记算法。
了解我们正在尝试解决的问题而不是我们用来解决问题的算法会很有帮助。 所以我们会说所有具有良好扩展算法的问题都“在 P 中”。 那些具有较差扩展性的算法是“NP”。
这意味着许多简单的问题也是“NP”问题，因为我们可以编写糟糕的算法来解决简单的问题。 知道 NP 中的哪些问题是真正棘手的问题固然很好，但我们不仅仅是想说“这是我们还没有找到好的算法的问题”。 毕竟，我可以提出一个我认为需要超级惊人算法的问题（称之为 X）。 我告诉全世界，我能想出的解决 X 的最佳算法规模很糟糕，所以我认为 X 是一个非常棘手的问题。 但是明天，也许比我聪明的人发明了一种算法，可以解决 X 并且在 P 中。所以这不是一个很好的难题定义。
尽管如此，NP 中有很多问题没有人知道一个好的算法。 因此，如果我能够证明 X 是某种类型的问题：解决 X 的良好算法也可以以某种迂回的方式使用，以给出一个好的算法NP 中所有其他问题的算法。 现在人们可能更加确信 X 是一个真正棘手的问题。 在这种情况下，我们称 X 为 NP-Complete。
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
我听到过一个解释，那就是：”
NP 完备性可能是算法研究中比较神秘的想法之一。 “NP”代表“非确定性多项式时间”，是问题所属的复杂性类别的名称。 NP 复杂性类别的重要之处在于该类别中的问题可以通过多项式时间算法验证。
举个例子，考虑计算东西的问题。 假设桌子上有一堆苹果。 问题是“有多少个苹果？” 为您提供了一个可能的答案 8。您可以使用数苹果的算法在多项式时间内验证这个答案。 计算苹果的时间复杂度为 O(n)（即 Big-oh 表示法），因为计算每个苹果需要一步。 对于 n 个苹果，你需要 n 个步骤。 该问题属于 NP 复杂度类。
如果一个问题可以证明它在多项式时间内既是NP-Hard又是可验证，则该问题被归类为NP-complete。 无需太深入地讨论 NP-Hard，只需说某些问题尚未找到多项式时间解决方案即可。 也就是说，它需要类似 n! (n 阶乘) 步骤来解决它们。 但是，如果给您一个 NP 完全问题的解决方案，您可以在多项式时间内验证它。
NP 完全问题的一个典型例子是旅行商问题。”
作者：ApoxyButt
来自：http://www.everything2.com/title/NP-complete
I have heard an explanation, that is:"
NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the NP complexity class is that problems within that class can be verified by a polynomial time algorithm.
As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.
A problem is classified as NP-complete if it can be shown that it is both NP-Hard and verifiable in polynomial time. Without going too deeply into the discussion of NP-Hard, suffice it to say that there are certain problems to which polynomial time solutions have not been found. That is, it takes something like n! (n factorial) steps to solve them. However, if you're given a solution to an NP-Complete problem, you can verify it in polynomial time.
A classic example of an NP-Complete problem is The Traveling Salesman Problem."
The author: ApoxyButt
From: http://www.everything2.com/title/NP-complete
据我了解，
P 是一组可以通过确定性 TM 在多项式时间内解决的问题。
NP 是一组需要在多项式时间内解决非确定性 TM 的问题。
这意味着我们可以在每个实例花费多项式时间的情况下并行检查所有不同的变量组合。 如果问题可以解决，那么 TM 的这些并行实例中至少有一个会以“是”停止。
这也意味着，如果您可以对变量/解决方案做出正确的猜测，那么您只需要在多项式时间内检查其有效性。
NP-Hard 是问题比 NP 更难的集合。 这意味着 NP-Hard 问题比 NP 集中的任何问题都更困难。 即使使用图灵机的非确定性，这些问题也是指数级的。 因此并行计算对于解决这些问题没有帮助。
NP-Complete 是 NP 和 NP-Hard 的交集。 据我了解，
如果 NP 完全集合中的任何问题在多项式时间内确定可解，则整个 NP 完全集合在多项式时间内确定可解。 此外，由于 NP 完全问题至少与 NP 集中最难的问题一样难，因此 NP 集中的所有问题（与 NP 完全集中的问题相同或更容易）将受到确定性多项式运行时间的限制，将 P 集扩展到 NP 集，导致 P=NP。
如果我犯了任何错误，请告诉我。
As far as I understand
P is the set of problems which could be solved in polynomial time with a deterministic TM.
NP is the set of problems which requires a non-deterministic TM to be solved in polynomial time.
This means that we can check all different combinations of variables in parallel with each instance taking polynomial time. If the problem is solvable then at least one of those parallel instances of TM would halt with "yes".
This also means that if you could make a correct guess about the variables/solution then you just need to check it's validity in polynomial time.
NP-Hard is the set where problems are harder than NP. This means NP-Hard problem are more difficult than any problem in NP set. These problems are exponential even when using non-determinism of Turing machines. So parallel computation does not helps while solving these problems.
NP-Complete is the intersection set of NP and NP-Hard. According to what I understood,
If any problem in NP-Complete set is deterministically solvable in polynomial time, then the entire NP-Complete set is deterministically solvable in polynomial time. Also since NP-Complete problems are at least as hard as the hardest problem in the NP set, all problems in the NP set (which are equal or easier than the problems in NP-Complete set) will be bounded above by deterministically polynomial running time, expanding the P set over the NP set, resulting in P=NP.
Please let me know if I made any mistake.
上面对 NP 完全问题的定义是正确的，但我想我可能会夸夸其谈它们的哲学重要性，因为还没有人解决这个问题。
几乎所有你遇到的复杂问题都是 NP 完全问题。 这个类有一些非常基本的东西，它在计算上似乎与容易解决的问题不同。 它们有自己的味道，而且不难认出它们。 这基本上意味着任何中等复杂的算法都不可能让你精确地解决——调度、优化、打包、覆盖等。
但如果你遇到的问题是 NP Complete 的，也不是全部都会丢失。 人们研究近似算法是一个广阔且技术性很强的领域，这将为您提供接近 NP 完全问题的解决方案的保证。 其中一些是令人难以置信的强有力的保证——例如，对于 3sat，您可以通过非常明显的算法获得 7/8 的保证。 更好的是，实际上，有一些非常强大的启发式方法，它们擅长为这些问题提供很好的答案（但不能保证！）。
请注意，两个非常著名的问题——图同构和因式分解——不知道是 P 还是 NP。
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.