什么是 NP 问题和 NP 完全问题？
我正在努力理解什么是非确定性多项式时间问题和 NP 完全问题。我了解什么是多项式时间可解问题，并在维基百科中看到有关 NP 问题的内容。读完这篇文章后，我尝试思考一些示例问题。据我了解，无向中的深度优先搜索是 NP 完全的，因为如果图很大（例如如果图形尺寸很小，则为多项式。）
任何人都可以在不使用太多数学的情况下用简单的示例简要解释所有这些 NP 术语吗？
I am struggling to understand what are nondeterministic polynomial-time problems and NP-complete problems. I understand what polynomial-time solvable problems are, and saw in Wikipedia about NP problems. After reading about this I tried to think about some example problems. As I understand it, depth-first search in an undirected is NP-complete, since each decisions can be made nondeterministically (i.e if I made the wrong decision, I could instead try some other choice) if the graph is large (cit an be polynomial if graph size is small.)
Can anyone briefly explain all these NP terms with simple examples without using much maths?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
关于NP和NP完备性的思考方式有很多种。我将从NP的定义开始，然后讨论NP硬度，最后讨论NP完整性。
在较高的层次上，P 和 NP 是问题的类别。如果是是或否问题，则存在问题（a 决策问题）并且有一些算法可以在多项式时间内解决该问题。例如，“你能从这张图中的节点u到达节点v吗？”的问题。属于P，因为你可以用深度优先搜索来解决它。 （请注意，DFS 本身不在P 中，因为 DFS 是一种算法，而不是问题）。 P 中问题的另一个例子是检查序列是否按排序顺序排列。
如果是或否问题，则存在NP问题（决策问题），可以在多项式时间内验证正确答案。例如，一个经典的NP问题是看看，给定一组已知重量的权重，您是否可以选择一组重量恰好为k的权重（这称为子集和问题）。弄清楚是否存在具有该属性的一组权重可能很棘手，但是如果我给你一组我说我知道是正确的权重，你可以很容易地检查我是否给了你正确的权重通过将它们相加并查看它们的总计是否为 k 来设置权重。
NP 被称为“非确定性多项式”的原因是，思考 NP 的另一种方式是思考一种神奇的算法，它可以以某种方式猜测问题的正确答案在多项式时间内。也就是说，如果您可以编写一个算法，允许猜测问题的答案并在多项式时间内运行，那么您正在解决的问题就是NP。回到我们的权重示例，我们可以为该问题编写一个猜测算法，如下所示。首先，在线性时间内猜测哪一组权重是正确的权重组，然后将它们全部相加，看看它们的总和是否为 k。如果是这样，请报告答案是“是”。否则，说“不”。如果这个程序总是保证做出正确的猜测，那么给定有解决方案的问题的任何输入，它总是会找到一个解决方案并报告“是”，如果没有解决方案，它总是会猜测错误并报告“否”。
目前计算机科学中最基本、最重要的问题之一是，已知属于NP的问题是否也属于P。也就是说，如果我们可以轻松有效地（在多项式时间内）验证问题的答案，那么我们总能有效地（在多项式时间内）解决该问题吗？众所周知，P中的任何问题也是NP中的问题，因为您可以使用多项式时间算法产生答案，然后检查它是否正确，但没有人们已经找到了一种在多项式时间内解决NP中任意问题的方法。
其原因是NP中的一些问题被称为 NP-完全，这意味着（非正式地）它们至少与NP中的所有其他问题一样难。如果我们能够有效地（多项式时间）解决这些问题，那么我们就可以在多项式时间内解决NP中的每个问题。这将是一件大事，因为NP中有很多非常重要的问题，但我们目前还没有好的、快速的算法来解决。这也是 P = NP 问题，因为只需要一种算法就能证明一大类被认为难以解决的问题实际上可以有效解决。
更正式地说，如果在多项式时间内，NP 问题可以将任何其他 NP 问题的任何实例转换为 NP 问题，则该问题称为 NP 完全问题该问题的一个例子。上述权重问题就是这样一个问题，确定布尔公式是否有令人满意的赋值的问题也是这样一个问题< /a>，解决整数上的某些优化问题（整数编程），确定访问一组位置的最快路线（旅行推销员） ，或确定如何使用最少数量的频率分配城市中的手机信号塔（图表着色） 。甚至确定是否可以解决像 数独 和 扫雷 已知对于任意棋盘尺寸都是 NP 完备的。
（有些问题具有后一个属性 - NP 中的任何问题都可以有效地转换为该问题 - 但它们本身并不在 NP 中。这些问题称为 NP-困难。）
从实践的角度来看，如果您曾经被要求解决一个已知为NP完全或NP困难的问题，不要期望在任何合理的时间内找到精确的解决方案。在某些情况下，甚至不可能在任何精度内有效地近似解。您最好寻找替代问题来尝试解决，或者屈服于在大多数但并非所有情况下都表现良好的启发式解决方案。
至于你对 DFS 是 NP 完全的最初想法，只有问题可以是 NP 或 NP-完全的;算法不能。 DFS 是一种解决图可达性问题的算法 - 给定图中的两个节点，是否存在从第一个节点到第二个节点的路径？该问题属于NP问题，因为如果存在一条路径，则很容易检查，但它（可能）不是NP完全的，因为我们知道我们可以使用多项式时间内解决它DFS。
希望这有帮助！
There are many ways of thinking about NP and NP-completeness. I'll start with a definition of NP, then will talk about NP-hardness, and finally NP-completeness.
At a high level, P and NP are classes of problems. A problem is in P if is a yes-or-no question (a decision problem) and there is some algorithm that solves the problem in polynomial time. For example, the question of "can you get from node u to node v in this graph?" belongs to P because you can solve it with depth-first search. (Note that DFS itself is not in P, since DFS is an algorithm rather than a problem). Another example of a problem in P would be checking whether a sequence is in sorted order.
A problem is in NP if it is a yes-or-no question (a decision problem) where a correct answer can be verified in polynomial time. For example, a classic NP problem is seeing whether, given a set of weights of known weight, you can pick a set of weights that weighs exactly some amount k (this is called the subset sum problem). It might be tricky to figure out whether a set of weights with that property exists, but if I were to give you a set of weights that I said I knew was correct, you could very easily check whether or not I had given you the correct set of weights by just adding them up and seeing if they totaled k.
The reason that NP is called "nondeterministic polynomial" is that a different way of thinking about NP is to think about a magic algorithm that can somehow guess the correct answer to a problem in polynomial time. That is, if you can write an algorithm that is allowed to make guesses about the answer to a problem and runs in polynomial time, then the problem you are solving is in NP. To go back to our weights example, we could write such a guessing algorithm for the problem as follows. Start off by, in linear time, guessing which set of weights is the correct set of weights, then add them all up and see if they total k. If so, report that the answer is "yes." Otherwise, say "no." If this program is always guaranteed to make correct guesses, then given any input to the problem that has a solution it will always find one and report "yes," and if there is no solution it will always guess wrong and report "no."
One of the most fundamental and important questions in computer science right now is whether any problem that is known to be in NP is also in P. That is, if we can easily verify the answer to a problem efficiently (in polynomial time), can we always solve that problem efficiently (in polynomial time)? It is known that any problem in P is also a problem in NP, since you can use the polynomial time algorithm to produce an answer and then check whether it's correct, but no one has ever found a way to solve arbitrary problems in NP in polynomial time.
The reason for this is that some problems in NP are known as NP-complete, meaning that (informally) they are at least as hard as every other problem in NP. If we could solve these problems efficiently (polynomial time), then we could solve every problem in NP in polynomial time. This would be a huge deal, since there are a lot of problems in NP that are extremely important that we currently have no good, fast algorithms for. This is also the allure of the P = NP question, since all it would take would be one algorithm to show that an enormous class of problems presumed to be impractically hard to solve would actually be solvable efficiently.
More formally, a problem in NP is called NP-complete if, in polynomial time, you can transform any instance of any other NP problem into an instance of that problem. The above problem with weights is such a problem, as is the problem of determining whether a boolean formula has a satisfying assignment, solving certain optimization problems over the integers (integer programming), determining the fastest route to visit a set of locations (traveling salesman), or determining how to assign cell towers in a city using the smallest number of frequencies (graph coloring). Even determining whether it's possible to solve a game like Sudoku and minesweeper are known to be NP-complete for arbitrary board sizes.
(Some problems have this latter property - that any problem in NP can be converted efficiently into that problem - but aren't themselves in NP. Those problems are called NP-hard.)
From a practical perspective, if you are ever asked to solve a problem that is known to be NP-complete or NP-hard, don't expect to find an exact solution in any reasonable time. In some cases, it's not even possible to approximate solutions to within any precision efficiently. You are best off looking for an alternative problem to try to solve or to resign yourself to a heuristic solution that does well in most but not all cases.
As to your original thoughts about DFS being NP-complete, only problems can be in NP or be NP-complete; algorithms cannot. DFS is an algorithm for solving the graph reachability problem - given two nodes in a graph, is there a path from the first to the second? That problem is in NP because if there is a path it's easy to check, but it's (probably) not NP-complete because we know we can solve it in polynomial time using DFS.
Hope this helps!
我将尝试解析您的示例，希望借助网络上的所有其他资源您可以取得进展。
几个问题
I'm going to try to parse your example, hopefully with all the other resources on the web you can make progress.
A few issues
我在大学里学到了一条经验法则：如果给定一个解决方案，可以快速验证该解决方案（即在多项式时间内），则问题属于 NP 问题。
I was taught a rule of thumb in college: a problem is in NP if, given a solution, the solution can be verified quickly (i.e. in polynomial time).