什么是NP和NP完全问题？ [英] What are NP and NP-complete problems?

问题描述

我在努力了解什么是不确定的多项式时间问题和NP完全问题。我明白多项式时间解决的问题是，在维基百科看到了有关NP问题。看完这个后，我试着去思考一些示例问题。据我了解，在无向深度优先搜索是NP完全问题，因为每个决定可能不确定地进行（即，如果我做出了错误的决定，我可以代替尝试一些其他的选择），如果该图是大（CIT的是如果多项式曲线尺寸小。）

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.)

任何人都可以简单介绍一下这些NP条款与简单的例子，而无需使用多少数学？

Can anyone briefly explain all these NP terms with simple examples without using much maths?

推荐答案

有思考NP和NP完全性的许多方面。我将开始与NP的定义，然后将谈论NP-硬度，最后NP完全性。

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.

目前较高的水平，P与NP是类的问题。一个问题是P中，如果给定的输入问​​题，你可以找到在多项式时间内解决这个问题。例如，问题你可以从节点获得u到在该图中节点U？属于为P，因为你可以用深度优先搜索解决这个问题。 （请注意，DFS本身并不在P，因为DFS是的算法的，而不是一个的问题的）。 P中的一个问题的另一个例子是检查序列是否是在有序

At a high level, P and NP are classes of problems. A problem is in P if given an input to the problem, you can find a solution to that 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.

一个问题是NP，如果它是一个是或否的问题（一个的 决策问题 的）其中一个正确的答案可以在多项式时间内验证。例如，一个典型的NP问题是看是否给出一组已知重量的砝码，可以挑选一组权重，重量究竟有些量k（这就是所谓的的子集和问题）。这可能是棘手找出一组权重与属性是否存在，但如果我给你一组权重，我说我知道是正确的，你可以很容易地检查是否我曾经给你正确的组权重，只需加入他们，看他们是否总计ķ。

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.

之所以NP被称为非确定多项式是考虑NP以不同的方式是考虑一个神奇的算法，该算法能以某种方式猜测正确答案，在多项式时间的问题。也就是说，如果你可以写一个允许做出回答一个问题的猜测，并运行在多项式时间，那么你要解决的问题是NP算法。要回到我们的权重的例子，我们可以如下写出这样的猜测算法的问题。开始关闭的，以线性时间，猜测其权重的设定是正确的一组权重，再加入所有这些，看看他们是否全钾。如果是这样，报告说，答案是是。否则，说不。如果该程序始终保证做出正确的猜测，再给予任何输入到，有一个解决方案，它总是会找到一个和报告问题是的，如果没有解决它总是猜错的话，报告没有。

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."

之一，在计算机科学中最根本，最重要的问题，现在是已知的NP任何问题是否也是P.也就是说，如果我们可以轻松地验证答案高效的问题（在多项式时间），可我们总有效地解决这个问题（多项式时间）？据了解，P中的任何问题，也是NP问题，因为你可以用多项式时间算法来产生一个答案，然后检查它是否是正确的，但从来没有人找到了一个方法，可以把任意的问题NP成P中的一个问题有效。

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 turn an arbitrary problem in NP into a problem in P efficiently.

一个很好的方式去思考P VS NP是密码锁。如果我知道密码是什么，我可以很容易地确认，我已经得到它的权利，只需打开锁。如果我能神奇地猜的没错我第一次尝试的组合，它会很容易打开锁。但除此之外，如果我真的有尝试通过用手每一个可能的组合运行，这将需要一个非常长的时间，我才弄清楚什么组合了。

A good way to think about P vs NP is with a combination lock. If I know what the combination is, I can easily verify that I've got it right by just opening the lock. If I could magically guess the combination right on my first try, it would be easy to open the lock. But otherwise, if I actually have to try running through every possible combination by hand, it would take an extremely long time before I could figure out what the combination was.

这样做的原因是，在NP一些问题被称为的 NP完全 ，即（非正式）他们至少很难，因为在NP所有其他问题。如果我们能够有效（多项式时间）解决这些问题，那么我们就可以解决多项式时间NP每一个问题。这将是一个巨大的交易，因为有很多的NP，是非常重要的，我们现在有没有好，速度快的算法问题。这也是 P = NP问题的诱惑力，因为所有则需将一种算法表明，一个巨大的类问题presumed是不切实际难以解决实际上是可以解决的效率。

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.

更正式地说，在NP的问题被称为NP完全的话，在多项式时间内，你可以将任何其他NP问题的任何实例到这个问题的一个实例。与重量的上述问题是这样的问题，由于是确定一个布尔公式是否具有令人满意的分配问题，在整数解决某些优化问题（整数规划），确定最快的路线访问一组位置（旅行商），或确定如何使用在一个城市分配信号发射塔最小数目的频率（图着色）。即使确定是否有可能解决这样的比赛数独和的 被称为扫雷艇是NP完全任意电路板尺寸。

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.

从实用的角度来看，如果你被要求解决被称为是NP完全性或NP难（意思是说，至少很难，因为一切都在NP但可能更难）的问题，不要不要指望找到任何合理时间的精确解。在某些情况下，甚至不能有效地内的任何precision近似的解决方案。你最好身上寻找替代问题，试图解决或辞职自己一个启发式的解决方案，能够较好的大多数但不是所有的情况。

From a practical perspective, if you are ever asked to solve a problem that is known to be NP-complete or NP-hard (meaning that it is at least as hard as everything in NP but possibly much harder), 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.

至于你有关DFS是NP完全原创的想法，只有的问题的可在NP或NP完全;算法不能。 DFS是一种算法用于解决图形可达性问题 - 在给定的曲线图的两个节点，是有从第一到第二路径？这个问题是NP，因为如果有一条小路很容易检查，但它的（可能）不NP完全问题，因为我们知道我们可以使用DFS在多项式时间内解决这个问题。

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.

希望这有助于！

这篇关于什么是NP和NP完全问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！