The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting?
P = NP的问题可能是所有计算机科学中最着名的问题。这是什么意思?为什么它如此有趣?
Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :)
哦,为了额外的功劳,请发表声明的真相或虚假证明。 :)
6 个解决方案
#1
327
P stands for polynomial time. NP stands for non-deterministic polynomial time.
P代表多项式时间。 NP代表非确定性多项式时间。
Definitions:
-
Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant.
多项式时间意味着算法的复杂度为O(n ^ k),其中n是数据的大小(例如,要排序的列表中的元素数量),k是常量。
-
Complexity is time measured in the number of operations it would take, as a function of the number of data items.
复杂性是根据数据项的数量来计算的操作次数的时间。
-
Operation is whatever makes sense as a basic operation for a particular task. For sorting the basic operation is a comparison. For matrix multiplication the basic operation is multiplication of two numbers.
作为特定任务的基本操作,操作是有意义的。对于排序,基本操作是比较。对于矩阵乘法,基本操作是两个数相乘。
Now the question is, what does deterministic vs. non-deterministic mean. There is an abstract computational model, an imaginary computer called a Turing machine (TM). This machine has a finite number of states, and an infinite tape, which has discrete cells into which a finite set of symbols can be written and read. At any given time, the TM is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition. Amazingly enough, by carefully constructing states and transitions, you can design a TM, which is equivalent to any computer program that can be written. This is why it is used as a theoretical model for proving things about what computers can and cannot do.
现在的问题是,确定性与非确定性意味着什么。有一个抽象的计算模型,一个名为图灵机(TM)的虚拟计算机。该机器具有有限数量的状态和无限磁带,其具有离散的单元,可以在其中写入和读取有限的符号集。在任何给定时间,TM处于其状态之一,并且它正在查看磁带上的特定单元。根据它从该单元格中读取的内容,它可以将新符号写入该单元格,将磁带向前或向后移动一个单元格,然后进入不同的状态。这称为状态转换。令人惊讶的是,通过精心构建状态和转换,您可以设计一个TM,它相当于任何可以编写的计算机程序。这就是为什么它被用作证明计算机能做什么和不能做什么的理论模型。
There are two kinds of TM's that concern us here: deterministic and non-deterministic. A deterministic TM only has one transition from each state for each symbol that it is reading off the tape. A non-deterministic TM may have several such transition, i. e. it is able to check several possibilities simultaneously. This is sort of like spawning multiple threads. The difference is that a non-deterministic TM can spawn as many such "threads" as it wants, while on a real computer only a specific number of threads can be executed at a time (equal to the number of CPUs). In reality, computers are basically deterministic TMs with finite tapes. On the other hand, a non-deterministic TM cannot be physically realized, except maybe with a quantum computer.
这里有两种与我们有关的TM:确定性和非确定性。对于从磁带上读取的每个符号,确定性TM仅从每个状态进行一次转换。非确定性TM可能具有几个这样的转变,即。即它能够同时检查几种可能性。这有点像产生多个线程。不同之处在于,非确定性TM可以产生所需数量的“线程”,而在实际计算机上,一次只能执行特定数量的线程(等于CPU数量)。实际上,计算机基本上是带有限磁带的确定性TM。另一方面,除了量子计算机之外,不能物理地实现非确定性TM。
It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM. However, it is not clear how much time it will take. The statement P=NP means that if a problem takes polynomial time on a non-deterministic TM, then one can build a deterministic TM which would solve the same problem also in polynomial time. So far nobody have been able to show that it can be done, but nobody has been able to prove that it cannot be done, either.
已经证明,可以通过确定性TM来解决可由非确定性TM解决的任何问题。但是,目前尚不清楚需要多长时间。语句P = NP意味着如果问题在非确定性TM上采用多项式时间,则可以构建确定性TM,其也将在多项式时间内解决相同问题。到目前为止,没有人能够证明它可以完成,但是没有人能够证明它也无法完成。
NP-complete problem means an NP problem X, such that any NP problem Y can be reduced to X by a polynomial reduction. That implies that if anyone ever comes up with a polynomial-time solution to an NP-complete problem, that will also give a polynomial-time solution to any NP problem. Thus that would prove that P=NP. Conversely, if anyone were to prove that P!=NP, then we would be certain that there is no way to solve an NP problem in polynomial time on a conventional computer.
NP完全问题意味着NP问题X,使得任何NP问题Y可以通过多项式减少而减少到X.这意味着如果有人想出一个NP完全问题的多项式时间解决方案,那么这也将为任何NP问题提供多项式时间解决方案。因此,这将证明P = NP。相反,如果有人要证明P!= NP,那么我们可以肯定在传统计算机上无法在多项式时间内解决NP问题。
An example of an NP-complete problem is the problem of finding a truth assignment that would make a boolean expression containing n variables true.
For the moment in practice any problem that takes polynomial time on the non-deterministic TM can only be done in exponential time on a deterministic TM or on a conventional computer.
For example, the only way to solve the truth assignment problem is to try 2^n possibilities.
NP完全问题的一个例子是找到真值赋值的问题,该真值赋值将使包含n个变量的布尔表达式为真。实际上,在非确定性TM上需要多项式时间的任何问题只能在确定性TM或传统计算机上以指数时间进行。例如,解决真值分配问题的唯一方法是尝试2 ^ n种可能性。
#2
75
- A yes-or-no problem is in P (Polynomial time) if the answer can be computed in polynomial time.
- A yes-or-no problem is in NP (Non-deterministic Polynomial time) if a yes answer can be verified in polynomial time.
如果答案可以在多项式时间内计算,则在P(多项式时间)中是或否问题。
如果可以在多项式时间内验证是答案,则在NP(非确定性多项式时间)中是或否问题。
Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.
直觉上,我们可以看到,如果问题在P中,那么它在NP中。考虑到P中问题的潜在答案,我们可以通过简单地重新计算答案来验证答案。
Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?
不太明显,更难以回答的是,NP中的所有问题是否都在P中。我们能否在多项式时间内验证答案,这意味着我们可以在多项式时间内计算答案吗?
There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.
有许多重要的问题已知是NP完全的(基本上,如果任何这些问题被证明在P中,那么所有NP问题都被证明在P中)。如果P = NP,那么所有这些问题都将被证明具有有效的(多项式时间)解。
Most scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof for either conjecture, they will win US $1 million.
大多数科学家认为P!= NP。但是,尚未确定P = NP或P!= NP的证据。如果有人提供任何猜想的证据,他们将赢得100万美元。
#3
20
To give the simplest answer I can think of:
为了给出我能想到的最简单的答案:
Suppose we have a problem that takes a certain number of inputs, and has various potential solutions, which may or may not solve the problem for given inputs. A logic puzzle in a puzzle magazine would be a good example: the inputs are the conditions ("George doesn't live in the blue or green house"), and the potential solution is a list of statements ("George lives in the yellow house, grows peas, and owns the dog"). A famous example is the Traveling Salesman problem: given a list of cities, and the times to get from any city to any other, and a time limit, a potential solution would be a list of cities in the order the salesman visits them, and it would work if the sum of the travel times was less than the time limit.
假设我们遇到一个需要一定数量输入的问题,并且有各种可能的解决方案,这些解决方案可能会或可能不会解决给定输入的问题。拼图杂志中的逻辑谜题就是一个很好的例子:输入是条件(“乔治不住在蓝色或温室里”),潜在的解决方案是一系列陈述(“乔治生活在黄色房子,种豌豆,并拥有狗“)。一个着名的例子是旅行商问题:给出一个城市列表,从任何城市到任何其他城市的时间和时间限制,潜在的解决方案将是销售人员访问它们的顺序的城市列表,以及如果旅行时间的总和小于时间限制,它将起作用。
Such a problem is in NP if we can efficiently check a potential solution to see if it works. For example, given a list of cities for the salesman to visit in order, we can add up the times for each trip between cities, and easily see if it's under the time limit. A problem is in P if we can efficiently find a solution if one exists.
如果我们能够有效地检查潜在的解决方案以确定它是否有效,那么这个问题就出现在NP中。例如,给定销售员按顺序访问的城市列表,我们可以将城市之间每次旅行的时间相加,并轻松查看是否在时间限制之内。如果我们能够有效地找到解决方案(如果存在的话),则问题在于P.
(Efficiently, here, has a precise mathematical meaning. Practically, it means that large problems aren't unreasonably difficult to solve. When searching for a possible solution, an inefficient way would be to list all possible potential solutions, or something close to that, while an efficient way would require searching a much more limited set.)
(在这里,有效地具有精确的数学意义。实际上,这意味着大问题并非难以解决。在寻找可能的解决方案时,一种效率低下的方法是列出所有可能的潜在解决方案,或者接近该解决方案的方法。虽然有效的方法需要搜索更有限的集合。)
Therefore, the P=NP problem can be expressed this way: If you can verify a solution for a problem of the sort described above efficiently, can you find a solution (or prove there is none) efficiently? The obvious answer is "Why should you be able to?", and that's pretty much where the matter stands today. Nobody has been able to prove it one way or another, and that bothers a lot of mathematicians and computer scientists. That's why anybody who can prove the solution is up for a million dollars from the Claypool Foundation.
因此,P = NP问题可以这样表达:如果您能够有效地验证上述排序问题的解决方案,您能找到有效的解决方案(或证明没有)吗?显而易见的答案是“你为什么能够这样做?”,这就是今天的问题所在。没有人能够以某种方式证明这一点,这困扰了许多数学家和计算机科学家。这就是为什么任何能够证明这个解决方案的人都能从Claypool基金会赚到一百万美元。
We generally assume that P does not equal NP, that there is no general way to find solutions. If it turned out that P=NP, a lot of things would change. For example, cryptography would become impossible, and with it any sort of privacy or verifiability on the Internet. After all, we can efficiently take the encrypted text and the key and produce the original text, so if P=NP we could efficiently find the key without knowing it beforehand. Password cracking would become trivial. On the other hand, there's whole classes of planning problems and resource allocation problems that we could solve effectively.
我们通常假设P不等于NP,没有找到解决方案的一般方法。如果事实证明P = NP,很多事情都会发生变化。例如,密码学将变得不可能,并且在互联网上具有任何形式的隐私或可验证性。毕竟,我们可以有效地获取加密的文本和密钥并生成原始文本,因此如果P = NP,我们可以在不事先知道的情况下有效地找到密钥。密码破解将变得微不足道。另一方面,我们可以有效地解决各类规划问题和资源分配问题。
You may have heard the description NP-complete. An NP-complete problem is one that is NP (of course), and has this interesting property: if it is in P, every NP problem is, and so P=NP. If you could find a way to efficiently solve the Traveling Salesman problem, or logic puzzles from puzzle magazines, you could efficiently solve anything in NP. An NP-complete problem is, in a way, the hardest sort of NP problem.
您可能听说过NP-complete的描述。 NP完全问题是NP(当然),并且具有这个有趣的特性:如果它在P中,则每个NP问题都是,因此P = NP。如果您能找到一种有效解决旅行商问题的方法,或者从拼图杂志中找到逻辑难题,您可以有效地解决NP中的任何问题。在某种程度上,NP完全问题是NP问题中最难的问题。
So, if you can find an efficient general solution technique for any NP-complete problem, or prove that no such exists, fame and fortune are yours.
所以,如果你能找到一个有效的通用解决方案技术来解决任何NP完全问题,或者证明不存在这样的问题,那么名誉和财富都属于你。
#4
9
A short summary from my humble knowledge:
我谦虚知识的简短摘要:
There are some easy computational problems (like finding the shortest path between two points in a graph), which can be calculated pretty fast ( O(n^k), where n is the size of the input and k is a constant (in the case of graphs, it's the number of vertexes or edges)).
有一些简单的计算问题(比如找到图中两点之间的最短路径),可以非常快速地计算(O(n ^ k),其中n是输入的大小,k是常数(在图的情况,它是顶点或边的数量))。
Other problems, like finding a path that crosses every vertex in a graph or getting the RSA private key from the public key is harder (O(e^n)).
其他问题,如找到跨越图中每个顶点的路径或从公钥获取RSA私钥更难(O(e ^ n))。
But CS speak tells that the problem is that we cannot 'convert' a non-deterministic Turing-machine to a deterministic one, we can, however, transform non-deterministic finite automatons (like the regex parser) into deterministic ones (well, you can, but the run-time of the machine will take long). That is, we have to try every possible path (usually smart CS professors can exclude a few ones).
但是CS说话的问题在于我们无法将非确定性图灵机“转换”为确定性机器,但是,我们可以将非确定性有限自动机(如正则表达式解析器)转换为确定性机器人(嗯,你可以,但机器的运行时间将花费很长时间)。也就是说,我们必须尝试所有可能的路径(通常聪明的CS教授可以排除几个)。
It's interesting because nobody even has any idea of the solution. Some say it's true, some say it's false, but there is no consensus. Another interesting thing is that a solution would be harmful for public/private key encryptions (like RSA). You could break them as easily as generating an RSA key is now.
这很有趣,因为没有人对解决方案有任何想法。有人说这是真的,有人说这是错误的,但没有达成共识。另一个有趣的事情是,解决方案对公钥/私钥加密(如RSA)有害。您可以像现在生成RSA密钥一样轻松破解它们。
And it's a pretty inspiring problem.
这是一个非常鼓舞人心的问题。
#5
6
There is not much I can add to the what and why of the P=?NP part of the question, but in regards to the proof. Not only would a proof be worth some extra credit, but it would solve one of the Millennium Problems. An interesting poll was recently conducted and the published results (PDF) are definitely worth reading in regards to the subject of a proof.
我没有太多可以添加问题的P =?NP部分的内容和原因,但是关于证明。一个证据不仅值得一些额外的功劳,而且它将解决千年问题之一。最近进行了一项有趣的民意调查,发表的结果(PDF)绝对值得阅读证明主题。
#6
5
First, some definitions:
首先,一些定义:
-
A particular problem is in P if you can compute a solution in time less than
n^kfor somek, wherenis the size of the input. For instance, sorting can be done inn log nwhich is less thann^2, so sorting is polynomial time.如果你可以计算一个k的时间小于n ^ k的解决方案,那么一个特殊的问题在于P,其中n是输入的大小。例如,排序可以在小于n ^ 2的n log n中完成,因此排序是多项式时间。
-
A problem is in NP if there exists a
ksuch that there exists a solution of size at mostn^kwhich you can verify in time at mostn^k. Take 3-coloring of graphs: given a graph, a 3-coloring is a list of (vertex, color) pairs which has sizeO(n)and you can verify in timeO(m)(orO(n^2)) whether all neighbors have different colors. So a graph is 3-colorable only if there is a short and readily verifiable solution.问题在于NP,如果存在k,使得存在最大n ^ k的大小的解,您可以在时间上最多验证n ^ k。对图形进行三色着色:给定一个图形,三色着色是(顶点,颜色)对的列表,其大小为O(n),您可以及时验证O(m)(或O(n ^ 2) )是否所有邻居都有不同的颜色。因此,只有存在简短且易于验证的解决方案时,图表才可以进行3次着色。
An equivalent definition of NP is "problems solvable by a Nondeterministic Turing machine in Polynomial time". While that tells you where the name comes from, it doesn't give you the same intuitive feel of what NP problems are like.
NP的等价定义是“在多项式时间内由非确定性图灵机解决的问题”。虽然这可以告诉您名称的来源,但它并没有给出与NP问题相同的直观感觉。
Note that P is a subset of NP: if you can find a solution in polynomial time, there is a solution which can be verified in polynomial time--just check that the given solution is equal to the one you can find.
请注意,P是NP的子集:如果您可以在多项式时间内找到解,那么可以在多项式时间内验证解决方案 - 只需检查给定的解决方案是否与您能找到的解决方案相同。
Why is the question P =? NP interesting? To answer that, one first needs to see what NP-complete problems are. Put simply,
为什么问题P =? NP有意思吗?要回答这个问题,首先需要了解NP完全问题是什么。简单地说,
- A problem L is NP-complete if (1) L is in P, and (2) an algorithm which solves L can be used to solve any problem L' in NP; that is, given an instance of L' you can create an instance of L that has a solution if and only if the instance of L' has a solution. Formally speaking, every problem L' in NP is reducible to L.
如果(1)L在P中,则问题L是NP完全的,并且(2)解决L的算法可以用于解决NP中的任何问题L';也就是说,给定L'的实例,当且仅当L'的实例有解决方案时,您才能创建具有解决方案的L实例。从形式上讲,NP中的每个问题L'都可以简化为L.
Note that the instance of L must be polynomial-time computable and have polynomial size, in the size of L'; that way, solving an NP-complete problem in polynomial time gives us a polynomial time solution to all NP problems.
注意,L的实例必须是多项式时间可计算的,并且具有多项式大小,大小为L';这样,在多项式时间内求解NP完全问题就可以得到所有NP问题的多项式时间解。
Here's an example: suppose we know that 3-coloring of graphs is an NP-hard problem. We want to prove that deciding the satisfiability of boolean formulas is an NP-hard problem as well.
这是一个例子:假设我们知道图的3色是一个NP难问题。我们想证明决定布尔公式的可满足性也是一个NP难问题。
For each vertex v, have two boolean variables v_h and v_l, and the requirement (v_h or v_l): each pair can only have the values {01, 10, 11}, which we can think of as color 1, 2 and 3.
对于每个顶点v,有两个布尔变量v_h和v_l,以及需求(v_h或v_l):每对只能有值{01,10,11},我们可以将其视为颜色1,2和3。
For each edge (u, v), have the requirement that (u_h, u_l) != (v_h, v_l). That is,
对于每个边(u,v),要求(u_h,u_l)!=(v_h,v_l)。那是,
not ((u_h and not u_l) and (v_h and not v_l) or ...)enumerating all the equal configurations and stipulation that neither of them are the case.not((u_h而不是u_l)和(v_h而不是v_l)或......)枚举所有相同的配置和规定,它们都不是这种情况。
AND'ing together all these constraints gives a boolean formula which has polynomial size (O(n+m)). You can check that it takes polynomial time to compute as well: you're doing straightforward O(1) stuff per vertex and per edge.
并且所有这些约束一起给出一个具有多项式大小(O(n + m))的布尔公式。您可以检查计算也需要多项式时间:每个顶点和每个边缘都在做直接的O(1)。
If you can solve the boolean formula I've made, then you can also solve graph coloring: for each pair of variables v_h and v_l, let the color of v be the one matching the values of those variables. By construction of the formula, neighbors won't have equal colors.
如果你可以解决我所做的布尔公式,那么你也可以解决图形着色:对于每对变量v_h和v_l,让v的颜色与那些变量的值匹配。通过构造公式,邻居将不具有相同的颜色。
Hence, if 3-coloring of graphs is NP-complete, so is boolean-formula-satisfiability.
因此,如果图的3色是NP完全的,那么布尔公式可满足性也是如此。
We know that 3-coloring of graphs is NP-complete; however, historically we have come to know that by first showing the NP-completeness of boolean-circuit-satisfiability, and then reducing that to 3-colorability (instead of the other way around).
我们知道图的三色是NP完全的;然而,历史上我们已经知道,首先显示布尔电路可满足性的NP完全性,然后将其降低到3可着色性(而不是相反)。
#1
327
P stands for polynomial time. NP stands for non-deterministic polynomial time.
P代表多项式时间。 NP代表非确定性多项式时间。
Definitions:
-
Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant.
多项式时间意味着算法的复杂度为O(n ^ k),其中n是数据的大小(例如,要排序的列表中的元素数量),k是常量。
-
Complexity is time measured in the number of operations it would take, as a function of the number of data items.
复杂性是根据数据项的数量来计算的操作次数的时间。
-
Operation is whatever makes sense as a basic operation for a particular task. For sorting the basic operation is a comparison. For matrix multiplication the basic operation is multiplication of two numbers.
作为特定任务的基本操作,操作是有意义的。对于排序,基本操作是比较。对于矩阵乘法,基本操作是两个数相乘。
Now the question is, what does deterministic vs. non-deterministic mean. There is an abstract computational model, an imaginary computer called a Turing machine (TM). This machine has a finite number of states, and an infinite tape, which has discrete cells into which a finite set of symbols can be written and read. At any given time, the TM is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition. Amazingly enough, by carefully constructing states and transitions, you can design a TM, which is equivalent to any computer program that can be written. This is why it is used as a theoretical model for proving things about what computers can and cannot do.
现在的问题是,确定性与非确定性意味着什么。有一个抽象的计算模型,一个名为图灵机(TM)的虚拟计算机。该机器具有有限数量的状态和无限磁带,其具有离散的单元,可以在其中写入和读取有限的符号集。在任何给定时间,TM处于其状态之一,并且它正在查看磁带上的特定单元。根据它从该单元格中读取的内容,它可以将新符号写入该单元格,将磁带向前或向后移动一个单元格,然后进入不同的状态。这称为状态转换。令人惊讶的是,通过精心构建状态和转换,您可以设计一个TM,它相当于任何可以编写的计算机程序。这就是为什么它被用作证明计算机能做什么和不能做什么的理论模型。
There are two kinds of TM's that concern us here: deterministic and non-deterministic. A deterministic TM only has one transition from each state for each symbol that it is reading off the tape. A non-deterministic TM may have several such transition, i. e. it is able to check several possibilities simultaneously. This is sort of like spawning multiple threads. The difference is that a non-deterministic TM can spawn as many such "threads" as it wants, while on a real computer only a specific number of threads can be executed at a time (equal to the number of CPUs). In reality, computers are basically deterministic TMs with finite tapes. On the other hand, a non-deterministic TM cannot be physically realized, except maybe with a quantum computer.
这里有两种与我们有关的TM:确定性和非确定性。对于从磁带上读取的每个符号,确定性TM仅从每个状态进行一次转换。非确定性TM可能具有几个这样的转变,即。即它能够同时检查几种可能性。这有点像产生多个线程。不同之处在于,非确定性TM可以产生所需数量的“线程”,而在实际计算机上,一次只能执行特定数量的线程(等于CPU数量)。实际上,计算机基本上是带有限磁带的确定性TM。另一方面,除了量子计算机之外,不能物理地实现非确定性TM。
It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM. However, it is not clear how much time it will take. The statement P=NP means that if a problem takes polynomial time on a non-deterministic TM, then one can build a deterministic TM which would solve the same problem also in polynomial time. So far nobody have been able to show that it can be done, but nobody has been able to prove that it cannot be done, either.
已经证明,可以通过确定性TM来解决可由非确定性TM解决的任何问题。但是,目前尚不清楚需要多长时间。语句P = NP意味着如果问题在非确定性TM上采用多项式时间,则可以构建确定性TM,其也将在多项式时间内解决相同问题。到目前为止,没有人能够证明它可以完成,但是没有人能够证明它也无法完成。
NP-complete problem means an NP problem X, such that any NP problem Y can be reduced to X by a polynomial reduction. That implies that if anyone ever comes up with a polynomial-time solution to an NP-complete problem, that will also give a polynomial-time solution to any NP problem. Thus that would prove that P=NP. Conversely, if anyone were to prove that P!=NP, then we would be certain that there is no way to solve an NP problem in polynomial time on a conventional computer.
NP完全问题意味着NP问题X,使得任何NP问题Y可以通过多项式减少而减少到X.这意味着如果有人想出一个NP完全问题的多项式时间解决方案,那么这也将为任何NP问题提供多项式时间解决方案。因此,这将证明P = NP。相反,如果有人要证明P!= NP,那么我们可以肯定在传统计算机上无法在多项式时间内解决NP问题。
An example of an NP-complete problem is the problem of finding a truth assignment that would make a boolean expression containing n variables true.
For the moment in practice any problem that takes polynomial time on the non-deterministic TM can only be done in exponential time on a deterministic TM or on a conventional computer.
For example, the only way to solve the truth assignment problem is to try 2^n possibilities.
NP完全问题的一个例子是找到真值赋值的问题,该真值赋值将使包含n个变量的布尔表达式为真。实际上,在非确定性TM上需要多项式时间的任何问题只能在确定性TM或传统计算机上以指数时间进行。例如,解决真值分配问题的唯一方法是尝试2 ^ n种可能性。
#2
75
- A yes-or-no problem is in P (Polynomial time) if the answer can be computed in polynomial time.
- A yes-or-no problem is in NP (Non-deterministic Polynomial time) if a yes answer can be verified in polynomial time.
如果答案可以在多项式时间内计算,则在P(多项式时间)中是或否问题。
如果可以在多项式时间内验证是答案,则在NP(非确定性多项式时间)中是或否问题。
Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.
直觉上,我们可以看到,如果问题在P中,那么它在NP中。考虑到P中问题的潜在答案,我们可以通过简单地重新计算答案来验证答案。
Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?
不太明显,更难以回答的是,NP中的所有问题是否都在P中。我们能否在多项式时间内验证答案,这意味着我们可以在多项式时间内计算答案吗?
There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.
有许多重要的问题已知是NP完全的(基本上,如果任何这些问题被证明在P中,那么所有NP问题都被证明在P中)。如果P = NP,那么所有这些问题都将被证明具有有效的(多项式时间)解。
Most scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof for either conjecture, they will win US $1 million.
大多数科学家认为P!= NP。但是,尚未确定P = NP或P!= NP的证据。如果有人提供任何猜想的证据,他们将赢得100万美元。
#3
20
To give the simplest answer I can think of:
为了给出我能想到的最简单的答案:
Suppose we have a problem that takes a certain number of inputs, and has various potential solutions, which may or may not solve the problem for given inputs. A logic puzzle in a puzzle magazine would be a good example: the inputs are the conditions ("George doesn't live in the blue or green house"), and the potential solution is a list of statements ("George lives in the yellow house, grows peas, and owns the dog"). A famous example is the Traveling Salesman problem: given a list of cities, and the times to get from any city to any other, and a time limit, a potential solution would be a list of cities in the order the salesman visits them, and it would work if the sum of the travel times was less than the time limit.
假设我们遇到一个需要一定数量输入的问题,并且有各种可能的解决方案,这些解决方案可能会或可能不会解决给定输入的问题。拼图杂志中的逻辑谜题就是一个很好的例子:输入是条件(“乔治不住在蓝色或温室里”),潜在的解决方案是一系列陈述(“乔治生活在黄色房子,种豌豆,并拥有狗“)。一个着名的例子是旅行商问题:给出一个城市列表,从任何城市到任何其他城市的时间和时间限制,潜在的解决方案将是销售人员访问它们的顺序的城市列表,以及如果旅行时间的总和小于时间限制,它将起作用。
Such a problem is in NP if we can efficiently check a potential solution to see if it works. For example, given a list of cities for the salesman to visit in order, we can add up the times for each trip between cities, and easily see if it's under the time limit. A problem is in P if we can efficiently find a solution if one exists.
如果我们能够有效地检查潜在的解决方案以确定它是否有效,那么这个问题就出现在NP中。例如,给定销售员按顺序访问的城市列表,我们可以将城市之间每次旅行的时间相加,并轻松查看是否在时间限制之内。如果我们能够有效地找到解决方案(如果存在的话),则问题在于P.
(Efficiently, here, has a precise mathematical meaning. Practically, it means that large problems aren't unreasonably difficult to solve. When searching for a possible solution, an inefficient way would be to list all possible potential solutions, or something close to that, while an efficient way would require searching a much more limited set.)
(在这里,有效地具有精确的数学意义。实际上,这意味着大问题并非难以解决。在寻找可能的解决方案时,一种效率低下的方法是列出所有可能的潜在解决方案,或者接近该解决方案的方法。虽然有效的方法需要搜索更有限的集合。)
Therefore, the P=NP problem can be expressed this way: If you can verify a solution for a problem of the sort described above efficiently, can you find a solution (or prove there is none) efficiently? The obvious answer is "Why should you be able to?", and that's pretty much where the matter stands today. Nobody has been able to prove it one way or another, and that bothers a lot of mathematicians and computer scientists. That's why anybody who can prove the solution is up for a million dollars from the Claypool Foundation.
因此,P = NP问题可以这样表达:如果您能够有效地验证上述排序问题的解决方案,您能找到有效的解决方案(或证明没有)吗?显而易见的答案是“你为什么能够这样做?”,这就是今天的问题所在。没有人能够以某种方式证明这一点,这困扰了许多数学家和计算机科学家。这就是为什么任何能够证明这个解决方案的人都能从Claypool基金会赚到一百万美元。
We generally assume that P does not equal NP, that there is no general way to find solutions. If it turned out that P=NP, a lot of things would change. For example, cryptography would become impossible, and with it any sort of privacy or verifiability on the Internet. After all, we can efficiently take the encrypted text and the key and produce the original text, so if P=NP we could efficiently find the key without knowing it beforehand. Password cracking would become trivial. On the other hand, there's whole classes of planning problems and resource allocation problems that we could solve effectively.
我们通常假设P不等于NP,没有找到解决方案的一般方法。如果事实证明P = NP,很多事情都会发生变化。例如,密码学将变得不可能,并且在互联网上具有任何形式的隐私或可验证性。毕竟,我们可以有效地获取加密的文本和密钥并生成原始文本,因此如果P = NP,我们可以在不事先知道的情况下有效地找到密钥。密码破解将变得微不足道。另一方面,我们可以有效地解决各类规划问题和资源分配问题。
You may have heard the description NP-complete. An NP-complete problem is one that is NP (of course), and has this interesting property: if it is in P, every NP problem is, and so P=NP. If you could find a way to efficiently solve the Traveling Salesman problem, or logic puzzles from puzzle magazines, you could efficiently solve anything in NP. An NP-complete problem is, in a way, the hardest sort of NP problem.
您可能听说过NP-complete的描述。 NP完全问题是NP(当然),并且具有这个有趣的特性:如果它在P中,则每个NP问题都是,因此P = NP。如果您能找到一种有效解决旅行商问题的方法,或者从拼图杂志中找到逻辑难题,您可以有效地解决NP中的任何问题。在某种程度上,NP完全问题是NP问题中最难的问题。
So, if you can find an efficient general solution technique for any NP-complete problem, or prove that no such exists, fame and fortune are yours.
所以,如果你能找到一个有效的通用解决方案技术来解决任何NP完全问题,或者证明不存在这样的问题,那么名誉和财富都属于你。
#4
9
A short summary from my humble knowledge:
我谦虚知识的简短摘要:
There are some easy computational problems (like finding the shortest path between two points in a graph), which can be calculated pretty fast ( O(n^k), where n is the size of the input and k is a constant (in the case of graphs, it's the number of vertexes or edges)).
有一些简单的计算问题(比如找到图中两点之间的最短路径),可以非常快速地计算(O(n ^ k),其中n是输入的大小,k是常数(在图的情况,它是顶点或边的数量))。
Other problems, like finding a path that crosses every vertex in a graph or getting the RSA private key from the public key is harder (O(e^n)).
其他问题,如找到跨越图中每个顶点的路径或从公钥获取RSA私钥更难(O(e ^ n))。
But CS speak tells that the problem is that we cannot 'convert' a non-deterministic Turing-machine to a deterministic one, we can, however, transform non-deterministic finite automatons (like the regex parser) into deterministic ones (well, you can, but the run-time of the machine will take long). That is, we have to try every possible path (usually smart CS professors can exclude a few ones).
但是CS说话的问题在于我们无法将非确定性图灵机“转换”为确定性机器,但是,我们可以将非确定性有限自动机(如正则表达式解析器)转换为确定性机器人(嗯,你可以,但机器的运行时间将花费很长时间)。也就是说,我们必须尝试所有可能的路径(通常聪明的CS教授可以排除几个)。
It's interesting because nobody even has any idea of the solution. Some say it's true, some say it's false, but there is no consensus. Another interesting thing is that a solution would be harmful for public/private key encryptions (like RSA). You could break them as easily as generating an RSA key is now.
这很有趣,因为没有人对解决方案有任何想法。有人说这是真的,有人说这是错误的,但没有达成共识。另一个有趣的事情是,解决方案对公钥/私钥加密(如RSA)有害。您可以像现在生成RSA密钥一样轻松破解它们。
And it's a pretty inspiring problem.
这是一个非常鼓舞人心的问题。
#5
6
There is not much I can add to the what and why of the P=?NP part of the question, but in regards to the proof. Not only would a proof be worth some extra credit, but it would solve one of the Millennium Problems. An interesting poll was recently conducted and the published results (PDF) are definitely worth reading in regards to the subject of a proof.
我没有太多可以添加问题的P =?NP部分的内容和原因,但是关于证明。一个证据不仅值得一些额外的功劳,而且它将解决千年问题之一。最近进行了一项有趣的民意调查,发表的结果(PDF)绝对值得阅读证明主题。
#6
5
First, some definitions:
首先,一些定义:
-
A particular problem is in P if you can compute a solution in time less than
n^kfor somek, wherenis the size of the input. For instance, sorting can be done inn log nwhich is less thann^2, so sorting is polynomial time.如果你可以计算一个k的时间小于n ^ k的解决方案,那么一个特殊的问题在于P,其中n是输入的大小。例如,排序可以在小于n ^ 2的n log n中完成,因此排序是多项式时间。
-
A problem is in NP if there exists a
ksuch that there exists a solution of size at mostn^kwhich you can verify in time at mostn^k. Take 3-coloring of graphs: given a graph, a 3-coloring is a list of (vertex, color) pairs which has sizeO(n)and you can verify in timeO(m)(orO(n^2)) whether all neighbors have different colors. So a graph is 3-colorable only if there is a short and readily verifiable solution.问题在于NP,如果存在k,使得存在最大n ^ k的大小的解,您可以在时间上最多验证n ^ k。对图形进行三色着色:给定一个图形,三色着色是(顶点,颜色)对的列表,其大小为O(n),您可以及时验证O(m)(或O(n ^ 2) )是否所有邻居都有不同的颜色。因此,只有存在简短且易于验证的解决方案时,图表才可以进行3次着色。
An equivalent definition of NP is "problems solvable by a Nondeterministic Turing machine in Polynomial time". While that tells you where the name comes from, it doesn't give you the same intuitive feel of what NP problems are like.
NP的等价定义是“在多项式时间内由非确定性图灵机解决的问题”。虽然这可以告诉您名称的来源,但它并没有给出与NP问题相同的直观感觉。
Note that P is a subset of NP: if you can find a solution in polynomial time, there is a solution which can be verified in polynomial time--just check that the given solution is equal to the one you can find.
请注意,P是NP的子集:如果您可以在多项式时间内找到解,那么可以在多项式时间内验证解决方案 - 只需检查给定的解决方案是否与您能找到的解决方案相同。
Why is the question P =? NP interesting? To answer that, one first needs to see what NP-complete problems are. Put simply,
为什么问题P =? NP有意思吗?要回答这个问题,首先需要了解NP完全问题是什么。简单地说,
- A problem L is NP-complete if (1) L is in P, and (2) an algorithm which solves L can be used to solve any problem L' in NP; that is, given an instance of L' you can create an instance of L that has a solution if and only if the instance of L' has a solution. Formally speaking, every problem L' in NP is reducible to L.
如果(1)L在P中,则问题L是NP完全的,并且(2)解决L的算法可以用于解决NP中的任何问题L';也就是说,给定L'的实例,当且仅当L'的实例有解决方案时,您才能创建具有解决方案的L实例。从形式上讲,NP中的每个问题L'都可以简化为L.
Note that the instance of L must be polynomial-time computable and have polynomial size, in the size of L'; that way, solving an NP-complete problem in polynomial time gives us a polynomial time solution to all NP problems.
注意,L的实例必须是多项式时间可计算的,并且具有多项式大小,大小为L';这样,在多项式时间内求解NP完全问题就可以得到所有NP问题的多项式时间解。
Here's an example: suppose we know that 3-coloring of graphs is an NP-hard problem. We want to prove that deciding the satisfiability of boolean formulas is an NP-hard problem as well.
这是一个例子:假设我们知道图的3色是一个NP难问题。我们想证明决定布尔公式的可满足性也是一个NP难问题。
For each vertex v, have two boolean variables v_h and v_l, and the requirement (v_h or v_l): each pair can only have the values {01, 10, 11}, which we can think of as color 1, 2 and 3.
对于每个顶点v,有两个布尔变量v_h和v_l,以及需求(v_h或v_l):每对只能有值{01,10,11},我们可以将其视为颜色1,2和3。
For each edge (u, v), have the requirement that (u_h, u_l) != (v_h, v_l). That is,
对于每个边(u,v),要求(u_h,u_l)!=(v_h,v_l)。那是,
not ((u_h and not u_l) and (v_h and not v_l) or ...)enumerating all the equal configurations and stipulation that neither of them are the case.not((u_h而不是u_l)和(v_h而不是v_l)或......)枚举所有相同的配置和规定,它们都不是这种情况。
AND'ing together all these constraints gives a boolean formula which has polynomial size (O(n+m)). You can check that it takes polynomial time to compute as well: you're doing straightforward O(1) stuff per vertex and per edge.
并且所有这些约束一起给出一个具有多项式大小(O(n + m))的布尔公式。您可以检查计算也需要多项式时间:每个顶点和每个边缘都在做直接的O(1)。
If you can solve the boolean formula I've made, then you can also solve graph coloring: for each pair of variables v_h and v_l, let the color of v be the one matching the values of those variables. By construction of the formula, neighbors won't have equal colors.
如果你可以解决我所做的布尔公式,那么你也可以解决图形着色:对于每对变量v_h和v_l,让v的颜色与那些变量的值匹配。通过构造公式,邻居将不具有相同的颜色。
Hence, if 3-coloring of graphs is NP-complete, so is boolean-formula-satisfiability.
因此,如果图的3色是NP完全的,那么布尔公式可满足性也是如此。
We know that 3-coloring of graphs is NP-complete; however, historically we have come to know that by first showing the NP-completeness of boolean-circuit-satisfiability, and then reducing that to 3-colorability (instead of the other way around).
我们知道图的三色是NP完全的;然而,历史上我们已经知道,首先显示布尔电路可满足性的NP完全性,然后将其降低到3可着色性(而不是相反)。