为什么 NP 问题被这样称呼（以及 NP 困难和 NP 完全）？
真的..本周二我将进行最后一次毕业考试，这是我永远无法理解的事情之一。 我意识到NP问题的解决方案可以在多项式时间内得到验证。但决定论与此有什么关系？
如果你能解释一下 NP-complete 和 NP-hard 的名字是从哪里来的，那就太好了（我很确定我明白它们的意思，我只是不明白它们的名字与它们的名字有什么关系）是）。
抱歉，如果这很微不足道，我似乎无法理解它（-：
谢谢大家！
Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand.
I realize that a solution for NP problem can be verfied in polynomial time. But what does determinism has to do with that?
And if you could explain me where NP-complete and NP-hard got their names, that would be great (I'm pretty sure I get the meaning of them, I just don't see what their names have to do with what they are).
Sorry if that's trivial, I just can't seem to get it (-:
Thanks all!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
P
类可以由确定性图灵机在多项式时间内解决的所有问题。
NP
可以通过非确定性图灵机在多项式时间内解决的所有问题的类别（它们也可以通过确定性图灵机在多项式时间内验证。）
NP -Hard
一类问题“至少与 NP 中最难的问题一样难”。形式上，一个问题是 NP-Hard 的，当且仅当存在一个 NP 完全问题，且该问题可在多项式时间图灵上还原； （另外：当且仅当它可以通过带有预言机的预言机在多项式时间内解决该问题）。这个名字的由来非常明显。
NPC
既是 NP 又是 NP-Hard 的问题类别。关于命名，甚至维基百科也不确定为什么这么命名。
P
Class of all problems which can be solved by a deterministic Turing machine in polynomial time.
NP
Class of all problems which can be solved by a non-deterministic Turing machine in polynomial time (they can also be verified by a deterministic Turing machine in polynomial time.)
NP-Hard
A class of problems which are "at least as hard as the hardest problems in NP". Formally, a problem is in NP-Hard iff there is an NP-complete problem that is polynomial time Turing-reducible to it; (also: iff it can be solved in polynomial time by an oracle machine with an oracle for the problem). It is pretty obvious where the name comes from.
NPC
The class of problems which are both NP as well as NP-Hard. Regarding the naming, even wikipedia is not sure why it's named as it is.
让我们从“非确定性”开始。确定性机器一次只能处于一种状态。我们实际上可以制造它们。不确定性机器是一种理论构造，一次可以处于多个状态。 （这里与量子计算有相似之处，但就我们的目的而言，它们具有误导性。忽略它们。）
如果我们想用确定性机器解决问题，我们启动它，它会经历一系列步骤来尝试发现问题。如果我们使用不确定性机器进行建模，它可以同时执行所有可能的一系列步骤。
我们要关心的一系列问题是决策问题：给定一个问题陈述，要么有解决方案，要么没有解决方案。寻找解决方案或报告没有解决方案。例如，假设您有一组逻辑语句：A 或非 B、B 或 C 或 D、非 D 或 A 或 B，...给定一个任意集合，您能否找到所有变量的真值这样所有的陈述都是正确的？
现在，让我们考虑 P。假设我们用 n 表示问题的大小。规模可以是旅行商问题中的城市数量、上述问题中逻辑语句的数量，等等。给定一定的 n，在给定系统上解决该问题将需要一定量的资源。现在，如果我们将资源或计算能力加倍，我们可以解决的问题的规模会发生什么变化？如果问题具有多项式复杂性，这意味着在 P 中，大小会增加一定比例。它可能会翻倍，或者上涨 40%，或者 10%。相反，如果它具有指数复杂度，则大小会增加一定数量。我们通常认为 P 问题是可解的，而指数问题是随着问题变大而无法解决的，尽管这是一种简化。从非正式的角度来看，多项式复杂性能够按顺序解决问题，而指数复杂性则必须考虑所有可能的组合。
假设我们可以在确定性机器上以多项式时间解决问题。问题在 P 中。假设我们可以在非确定性机器上以多项式时间解决它，这与能够在确定性机器上以多项式时间验证提出的解决方案是一样的。那么问题就出在NP上了。这里的技巧是我们无法制造真正的非确定性机器，因此问题属于 NP 的事实并不意味着它可以实际解决。
现在讨论 NP 完全问题。 P 中的所有问题都属于 NP。对于 NP 中的问题 A 和 B，我们也许可以说，如果 A 在 P 中，那么 B 也在 P 中。这是通过找到一种将 B 重述为 A 类问题的方法来完成的。 NP 完全问题是指，如果它在 P 中，则 NP 中的每个问题都在 P 中。正如您可能猜到的那样，找到一种方法将每个可能的问题重述为一个特定问题并不容易，我将只是说上面的逻辑陈述问题（可满足性问题）是第一个被证明的 NP 完全问题。之后就更容易了，因为只需证明如果问题 C 在 P 中，那么可满足性也在 P 中。
人们普遍认为存在 NP 问题而不是 P 问题，并且最近发布了一个证明（可能有效也可能无效）。在这种情况下，NP 完全程序是 NP 中最难的问题。
有些问题不适合这个模式。正如通常提出的那样，旅行商问题是找到连接所有城市的最便宜的路线。这不是一个决策问题，我们无法直接验证任何提出的解决方案。我们可以将其重述为决策问题：给定成本 C，是否存在比 C 更便宜的路线？这个问题是 NP 完全问题，只需做一点工作，我们就可以像解决修改后的 NP 完全形式一样轻松地解决原始 TSP。因此，TSP 是 NP 困难的，因为它至少与 NP 完全问题一样困难。
Let's start with "nondeterministic". A deterministic machine can be in one state at a time. We can actually make them. A nondeterministic machine is a theoretical construct that can be in more than one state at a time. (There's similarities to quantum computing here, but for our purposes here they're misleading. Disregard them.)
If we want to solve a problem with a deterministic machine, we start it up, and it goes through a series of steps to try to find a problem. If we model using a nondeterministic machine, it can go through all possible series of steps at the same time.
The set of problems we're going to be concerned with is decision problems: given a problem statement, either there is a solution or not. Find a solution or report that there is none. For example, assume you have a set of logical statements: A or not-B, B or C or D, not-D or A or B, .... Given an arbitrary set, can you find truth values for all the variables such that all the statements are true?
Now, let's consider the P. Suppose we represent the size of a problem by n. The size could be the number of cities in a traveling salesman problem, the number of logical statements in the problem above, whatever. Given a certain n, the problem will require a certain amount of resources to solve on a given system. Now, if we double the resources or computational ability, what happens to the size of the problem we can solve? If the problem is of polynomial complexity, which means in P, the size goes up by a certain fraction. It might double, or go up by 40%, or 10%. In contrast, if it's of exponential complexity, the size goes up by a certain number. We generally think of P problems as solvable and exponential problems as unsolvable as the problems get large, although that's a simplification. From an informal point of view, polynomial complexity is being able to figure things out about the problem sequentially, while exponential is having to look at all possible combinations.
Suppose we can solve the problem in polynomial time on a deterministic machine. The problem is in P. Suppose we can solve it in polynomial time on a nondeterministic machine, which is the same thing as being able to verify a proposed solution in polynomial time on a deterministic machine. Then the problem is in NP. The trick here is that we can't make true nondeterministic machines, so that the fact that a problem is in NP doesn't mean it's practical to solve.
Now on to NP-complete. All problems in P are in NP. For problems A and B in NP, we might be able to say that if A is in P, so is B. This is done by finding a way to restate B as an A sort of problem. An NP-complete problem is one such that, if it is in P, every problem in NP is in P. As you might guess, finding a way to restate every possible problem as one particular one wasn't easy, and I'll just say that the problem with logical statements above (the Satisfiability problem) was the first proved NP-complete. After that it was easier, since it was only necessary to prove that if problem C was in P, so was Satisfiability.
It's generally believed that there are problems that are in NP but not P, and a proof was recently published (which may or may not turn out to be valid). In that case, NP-complete programs are the hardest sorts of problems in NP.
There are problems that don't fit into this mold. The Traveling Salesman Problem, as normally posed, is to find the cheapest route connecting all cities. That isn't a decision problem, and we can't verify any proposed solution directly. We can restate it as a decision problem: given a cost C, is there a route that's cheaper than C? This problem is NP-complete, and with a little work we can solve the original TSP about as easily as the modified, NP-complete, form. Therefore, the TSP is NP-hard, since it's at least as hard as an NP-complete problem.
NP被称为NP（非确定性多项式时间），因为NP问题可以通过非确定性图灵机在多项式时间内解决。
NP is called NP (nondeterministic polynomial time) because an NP problem can be solved in polynomial time by a nondeterministic turing machine.
让我们从 NP 开始：在 NP 中，N 代表“不确定性”，P 代表“多项式时间”。如果你有一个非确定性图灵机，它可以在每个周期分支以并行探索可能性，那么它是可以在多项式时间内解决的一类问题（“验证解决方案”替代定义最近变得流行，但它并没有明确说明） “N”是什么意思）。不确定性机器可以与具有无限数量处理器的并行计算机进行比较，并且能够在每条指令上
fork()。说问题 Q 是“NP 难”意味着 NP 中的任何问题都可以简化为问题 Q（在多项式时间内）。由于问题之间的关系“可以简化为”是顺序关系，因此您可以将“NP-hard”视为“至少与所有 NP 问题一样难”。
“NP 完全”问题只是 NP 中的 NP 困难问题之一。我想这类问题需要一个名称，但我不确定如何解释“完整”这个词的选择。
Let's begin with NP: in NP, N is for "nondeterministic" and P is for "polynomial time". It is the class of problems that can be solved in polynomial time if you have a nondeterministic Turing machine that can branch at each cycle to explore possibilities in parallel (the "verify the solution" alternative definition has become popular recently but it does not make clear what "N" means). The nondeterministic machine can be compared to a parallel computer with an infinite number of processors, and the ability to
fork()at each instruction.Saying that a problem Q is "NP-hard" means that any problem in NP can be reduced to problem Q (in polynomial time). Since the relation "can be reduced to" between problems is an order relation, you can think of "NP-hard" as meaning "at least as hard as all NP problems".
An "NP-complete" problem is simply one of the problems in NP that is NP-hard. I guess that class of problems needed a name, but I'm not sure how to explain the choice of the word "complete".
来自 Wikipedia：
NP 是所有决策问题的集合，其中“是” -答案具有可有效验证的证据，证明答案确实是“是”。更准确地说，这些证明必须可以通过确定性图灵机在多项式时间内验证，
但不确定这些名称的历史。编辑：不过我有猜测。以下是猜测，但我认为不无道理。
NP-Hard 是至少与 NP 中最难问题一样难的任何问题。因此，可以说所讨论的问题具有 NP 硬度，即 NP-Hard。
如果 NP 完全中的任何单个问题都可以快速解决，那么 NP 中的每个问题也可以快速解决。因此，可以解决整套NP问题。
编辑2：维基百科的完整（复杂性）文章指出：
From Wikipedia:
NP is the set of all decision problems for which the 'yes'-answers have efficiently verifiable proofs of the fact that the answer is indeed 'yes'. More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine
Not sure about the history of the names though. EDIT: I have guesses though. What follows is speculation but I don't think it's unreasonable.
NP-Hard is any problem which is at least as hard as the hardest problems in NP. Therefore, it could be said that the problem in question would have NP hardness., hence NP-Hard.
If any single problem in NP-complete can be solved quickly, then every problem in NP can also be solved quickly. Therefore, the complete set of NP problems could be solved.
EDIT2: Wikipedia's Complete (Complexity) article indicates: