跳转到内容

P/NP问题：修订间差异

本页使用了标题或全文手工转换
维基百科，自由的百科全书
以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
Sz-iwbot（留言 | 贡献）
机器人
447,868次编辑
小 robot Adding: fr, ko
add unsolved on en
 
（未显示超过100个用户的204个中间版本）
第1行： 第1行：
{{noteTA
[[Image:Complexity classes.png|thumb|250px|假设'''P''' ≠ '''NP'''的复杂度类的图解.如'''P''' = '''NP'''则三个类相同.]]
|G1 = IT
}}
{{多個問題|
{{expert|subject=计算机科学|time=2012-07-28}}
{{Cleanup rewrite||翻译质量不佳，语调或风格不适合[[Wikipedia:更优秀条目写作指南#寫作風格|百科全书的写作方式]]，读起来亦像[[Wikipedia:维基百科不是什么#維基百科不是發表創新意念的地方|评论]]。|time=2022-11-27T03:56:00+00:00}}
{{Disputed|time=2022-11-27T03:56:00+00:00}}
|update=2022-5-18
}}
{{unsolved|計算機科學|如果一个问题的解可以快速检验正确性，那么这个问题一定可以快速求解吗？}}
{{千禧年难题}}


'''{{lang|en|P/NP}}问题'''是[[理论计算机科学]]中[[计算复杂度理论]]领域至今未解决的问题，是[[克雷数学研究所]]七題[[千禧年大奖难题]]之一。P/NP问题包括[[复杂度类]][[P (复杂度)|P]]与[[NP (复杂度)|NP]]的关系。1971年由[[史提芬·古克]]（Stephen A. Cook）和{{tsl|en|Leonid Levin|列昂尼德·列文}}分別提出。
{{translation}}
[[计算复杂度理论]]是[[计算理论]]处理解决给定问题所需的资源的一部分。最常见的资源就是时间(解决问题的步数)和空间(需要多少内存来解决问题)。


== P=NP ==<!--
In this theory, the class '''[[P (complexity)|P]]''' consists of all those [[decision problem|decision problems]] that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class '''[[NP (complexity)|NP]]''' consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in [[polynomial time]] on a [[Non-deterministic Turing machine | non-deterministic]] machine. Arguably, the biggest open question in [[theory of computation|theoretical computer science]] concerns the relationship between those two classes:
Die Komplexitätsklasse P beinhaltet alle Probleme, welche von deterministischen Turingmaschinen in polynomiell beschränkter Zeit gelöst werden können. Dagegen beinhaltet NP die Menge aller von nichtdeterministischen Turingmaschinen in polynomialzeit lösbaren Probleme. Aus diesen beiden Definitionen geht hervor, dass P eine Teilmenge von NP ist, unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist und die beiden Klassen somit identisch wären.-->
:Is '''P''' equal to '''NP'''?
复杂度类'''[[P (复杂度)|P]]'''即為所有可以由一个[[图灵机|确定型图灵机]]在[[多项式]]表达的时间内解决的问题；类'''[[NP (复杂度)|NP]]'''由所有可以在多项式时间内验证它的解是否正確的决定问题组成，或者等效的说，那些可以在[[非確定型圖靈機]]上在[[多项式时间]]内找出解的问题的集合。很可能，[[计算理论]]最大的未解决问题就是关于这两类的关系的：
In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.[http://www.cs.umd.edu/~gasarch/papers/poll.ps] A [[Clay Mathematics Institute|$1,000,000 USD prize]] has been offered for a correct solution.
:'''P'''和'''NP'''相等
在2002年对于100研究者的调查中，61人相信答案是否定的，9人相信答案是肯定的，22人不确定，而8人相信问题可能和现在所接受的公理独立，所以不可能证明或证否。<ref>{{cite web |title=Wayback Machine（网页存档） |url=http://www.cs.umd.edu/~gasarch/papers/poll.ps |website=web.archive.org |date=2005-04-04 |access-date=2017-09-05 |archive-date=2005-04-04 |archive-url=https://web.archive.org/web/20050404002304/http://www.cs.umd.edu/~gasarch/papers/poll.ps |dead-url=yes }}</ref>对于正确的解答，有一个[[克雷數學研究所|一百萬美元的奖励]]。


[[NP-完全]]问题（或者叫'''NPC'''）的集合在这讨论有重大作用，它们可以大致的描述为那些在'''NP'''中最不像在'''P'''中的（确切定义细节请参看[[NP-完全]]理论）。[[计算机科学家]]现在相信'''P'''、'''NP'''和'''NPC'''类之间的关系如图中所示，其中'''P'''和'''NPC'''类不相交。
An important role in this discussion is played by the set of [[NP-complete]] problems (or '''NPC''') which can be loosely described as those problems in '''NP''' that are the least likely to be in '''P'''. (See [[NP-complete]] for the exact definition.) Theoretical [[computer scientist]]s currently believe that the relationship among the classes '''P''', '''NP''', and '''NPC''' is as shown in the picture, with the '''P''' and '''NPC''' classes disjoint.
[[File:Complexity classes.svg|thumb|250px|假设'''P'''≠'''NP'''的复杂度类的图解。如'''P'''='''NP'''则三个类相同。]]


簡單來說，'''P'''='''NP'''即：「若问题的答案可以很快验证，其答案是否也可以很快被计算出來。」
In essence, the '''P''' = '''NP''' question asks: if positive solutions to a YES/NO problem can be ''verified'' quickly, can the answers also be ''computed'' quickly? Here is an example to get a feeling for the question. Given a large number ''Y'', we might ask whether ''Y'' is a [[composite number]]. For example, we might ask whether the number 53308290611 has nontrivial factors. The answer is YES, though it would take a fair amount of work to find a factor by hand. On the other hand, if someone claims that the answer is "YES, because 224737 is a divisor of 53308290611", then we can quickly check that with a single division. Verifying that a number is a divisor is much easier than finding the divisor in the first place. The information needed to verify a positive answer is also called a ''certificate''. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in '''NP'''. Although this particular problem was recently shown to be in '''P''' as well (see references for "PRIMES in P" [[#External links and references|below]]), this is not at all obvious, and there are many other similar problems that are not believed to be in '''P'''.


例如某大数是否[[合数]]：如53308290611有否非平凡[[因數]]。答案是肯定的，虽然人手找出一个因數很麻烦。从另一个方面讲，如果有人声称答案是「对，224737可以整除53308290611」，则我们可以很快用除法验证。验证一个数是除数比找出一個明顯除数来简单得多。用於验证一个正面答案所需的信息也称为'''[[证明]]'''。所以我们的结论是，给定正确的证明，问题的正面答案可以很快（也就是，在多项式时间内）验证，而这就是这个问题属于'''NP'''的原因。
The restriction to YES/NO problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether [[FP (complexity)|FP]] = [[FNP (complexity)|FNP]]) is equivalent.


虽然这个特定的问题，最近也獲证實在'''P'''类中（参看[[#外部链接和参考|下面的]]关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类'''P'''。
==Formal definitions==


像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否[[FP (复杂度)|FP]]=[[FNP (复杂度)|FNP]]）是等价的。
More formally, a ''decision problem'' is a problem that takes as input some [[String (computer science)|string]] and requires as output either YES or NO. If there is an [[algorithm]] (say a [[Turing machine]], or a [[Lisp programming language|LISP]] or [[Pascal programming language|Pascal]] program with unbounded memory) which is able to produce the correct answer for any input string of length ''n'' in at most ''n''<sup>''k''</sup> steps, where ''k'' is some constant independent of the input string, then we say that the problem can be solved in ''polynomial time'' and we place it in the class '''P'''. Intuitively, we think of the problems in '''P''' as those that can be solved reasonably quickly.


== 学术定义 ==
Now suppose there is an algorithm A(''w'',''C'') which takes two arguments, a string ''w'' which is an input string to our decision problem, and a string ''C'' which is a "proposed certificate", and such that A produces a YES/NO answer in at most ''n''<sup>''k''</sup> steps (where ''n'' is the length of ''w'' and ''k'' doesn't depend on ''w''). Suppose furthermore that
: ''w'' is a YES instance of the decision problem if and only if there exists ''C'' such that A(''w'',''C'') returns YES.
Then we say that the problem can be solved in ''non-deterministic polynomial time'' and we place it in the class '''NP'''. We think of the algorithm A as a verifier of proposed certificates which runs reasonably fast. (Note that the abbreviation '''NP''' stands for "'''N'''on-deterministic '''P'''olynomial" and ''not'' for "'''N'''on-'''P'''olynomial".)


更正式一些，一个'''决定问题'''是一个取一些[[字符串]]为输入并要求输出为是或否的问题。若有一个[[算法]]（譬如[[图灵机]]，或一个[[Lisp|LISP]]或[[Pascal编程语言|Pascal]]的程序并有无限的内存）能够在最多'''n'''<sup>'''k'''</sup>步内对一个串长度为'''n'''的输入给出正确答案，其中'''k'''是某个不依赖于输入串的常数，则我们称该问题可以在'''多项式时间'''内解决，并且将它置入类'''P'''。直观的讲，我们将'''P'''中的问题视为可以较快解决的问题。
==NP-complete==


现在假设有一个算法A('''w''','''C''')取两个参数，一个串'''w'''，也就是我们的决定问题的输入串，而另一个串'''C'''是“建议证明”，并且使得A在最多'''n'''<sup>'''k'''</sup>步内产生“是／否”答案（其中'''n'''是'''w'''的长度而'''k'''不依赖于'''w'''）。然後假设：'''w'''是一个答案为“是”的例子，当且仅当，存在'''C'''使得A('''w''','''C''')返回“是”。
To attack the '''P''' = '''NP''' question, the concept of [[NP-Complete|'''NP'''-completeness]] is very useful. Informally, the '''NP'''-complete problems are the "toughest" problems in '''NP''' in the sense that they are the ones most likely not to be in '''P'''. This is because ''any'' problem in '''NP''' can be transformed, in polynomial time, into an instance of any specific '''NP'''-complete problem. For instance, the decision problem version of the [[traveling salesman problem]] is '''NP'''-complete. So ''any'' instance of ''any'' problem in '''NP''' can be transformed mechanically into an instance of the traveling salesman problem, in polynomial time. So, if the traveling salesman problem turned out to be in '''P''', then '''P ''' = '''NP'''! The traveling salesman problem is one of many such '''NP'''-complete problems. If any '''NP'''-complete problem is in '''P''', then it would follow that '''P''' = '''NP'''. Unfortunately, many important problems have been shown to be '''NP'''-complete and not a single fast algorithm for any of them is known.
则我们称这个问题可以在'''非决定性多项式时间'''内解决，且将它放入'''NP'''类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写'''NP'''代表“'''N'''on-deterministic（非确定性）'''P'''olynomial（多项式）”而不是代表“'''N'''on-'''P'''olynomial（非多项式）。）


==Still harder problems==
== NP完全 ==


要解决'''P'''='''NP'''问题，[[NP完全|'''NP'''完全]]的概念非常有用。不严格的讲，'''NP'''完全问题是'''NP'''类中“最难”的问题，也就是说它们是最可能不属于'''P'''类的。这是因为'''任何NP'''中的问题可以在多项式时间内变换成为任何特定'''NP'''完全问题的一个特例。例如，[[旅行推销员问题]]的判定问题版本为'''NP'''完全。所以'''NP'''中的'''任何'''问题的'''任何'''特例可以在多项式时间内转换成旅行商问题的一个特例。所以若旅行商问题能证實在'''P'''内，则'''P'''='''NP'''。旅行商问题是很多这样的'''NP'''完全的问题之一。若任何一个'''NP'''完全的问题在'''P'''内，则可以推出'''P'''='''NP'''。不幸的是，虽然很多重要的问题被证實为'''NP'''完全，但却没有一个有已知快速的算法。
Although it is unknown whether '''P'''='''NP''', problems outside of '''P''' are known. The problem of finding the best move in [[Chess]] or [[Go (board game)|Go]] (on an ''n'' by ''n'' board) is [[EXPTIME-complete]]. Because it can be shown that P &ne; EXPTIME, these problems are outside '''P''', and so require more than polynomial time. The problem of deciding the truth of a statement in [[Presburger arithmetic]] is even harder. Fischer and [[Michael O. Rabin|Rabin]] proved in [[1974]] that every algorithm which decides the truth of Presburger statements has a runtime of at least 2^(2^(''cn'')) for some constant ''c''. Here, ''n'' is the length of the Presburger statement. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the [[halting problem]]. They cannot be solved in general given any amount of time.


== Is P really tractable? ==
== 更难的问题 ==


虽然是否'''P'''='''NP'''还是未知的，在'''P'''之外的问题是已经知道存在的。寻找[[国际象棋]]或[[围棋]]最佳走法（在''n''乘''n''棋盘上）是[[NP困难]]的。因为可以证明P≠EXPTIME（指数时间），这些问题位于'''P'''之外，所以需要比多项式时间更多的时间。判定{{tsl|en|Presburger arithmetic|皮尔斯伯格算术}}中的命题是否为真的问题更加困难。Fischer和{{tsl|en|Michael O. Rabin|Rabin}}于1974年证明每个决定Presburger命题的真伪性的算法有最少2<sup>2<sup>cn</sup></sup>的运行时间，''c''为某个常数。这裡，''n''是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如[[停机问题]]，而它们无法在任何给定时间内解决。
All of the above discussion has assumed that '''P''' means "easy" and "not in '''P'''" means "hard". While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
*It ignores constant factors. A problem that takes time 10<sup>1000</sup>''n'' is '''P''' (it is linear time), but is completely intractable in practice. A problem that takes time 10<sup>-10000</sup>2<sup>''n''</sup> is not '''P''' (it is exponential time), but is very tractable for values of ''n'' up into the thousands.
*It ignores the size of the exponents. A problem with time ''n''<sup>1000</sup> is '''P''', yet intractable. Problems have been proven to exist in '''P''' that require arbitrarily large exponents (see [[time hierarchy theorem]]). A problem with time 2<sup>''n''/1000</sup> is not '''P''', yet is tractable for ''n'' up into the thousands.
*It only considers worst-case times. There might be a problem that arises in the real world such that most of the time, it can be solved in time ''n'', but on very rare occasions you'll see an instance of the problem that takes time 2<sup>''n''</sup>. This problem might have an average time that is polynomial, but the worst case is exponential, so the problem wouldn't be in '''P'''.
*It only considers deterministic solutions. There might be a problem that you can solve quickly if you accept a tiny error probability, but a guaranteed correct answer is much harder to get. The problem would not belong to '''P''' even though in practice it can be solved fast. This is in fact a common approach to attack problems in '''NP''' not known to be in '''P''' (see '''[[RP (complexity)|RP]]''', '''[[BPP]]''').
*New computing models such as [[quantum computer]]s, may be able to quickly solve some problems not known to be in '''P'''; however, none of the problems they are known to be able to solve are '''NP'''-hard. However, it should be noted that the ''definition'' of '''P''' and '''NP''' are in terms of classical computing models like Turing machines. Therefore, even if a quantum computer algorithm were discovered to efficiently solve an '''NP'''-hard problem, we would only have a way of physically solving difficult problems quickly, not a proof that the mathematical classes '''P''' and '''NP''' are equal.


== P真的容易处理吗？ ==
==Why do computer scientists think P &ne; NP?==
上面所有的讨论，假设了'''P'''表示“容易”而“不在'''P'''中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
* 它忽略了常数因子。一个需要10<sup>1000</sup>''n''时间的问题是属于'''P'''的（它是线性时间的），但是事实上完全无法处理。一个需要10<sup>-10000</sup>2<sup>''n''</sup>时间的问题不是在'''P'''中的（它是指数时间的），但是对于''n''取值直到几千时还是很容易处理的。
* 它忽略了指数的大小。一个时间复杂度''n''<sup>1000</sup>属于'''P'''，但是很难对付。已经证明在'''P'''中存在需要任意大的指数的问题（参看[[时间层次定理]]）。一个时间复杂度2<sup>''n''/1000</sup>的问题不属于'''P'''，但对于''n''直到几千还是容易应对的。
* 它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间''n''中解决，但是很偶尔你会看到需要时间2<sup>''n''</sup>的特例。这问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于'''P'''。
* 它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于'''P'''，虽然事实上它可以很快求解。这实际上是解决属于'''NP'''而还不知道是否属于'''P'''的问题的一个办法（参看'''[[RP (复杂度)|RP]]'''，'''[[BPP_(複雜度)|BPP]]'''）。
* 新的诸如[[量子计算机]]这样的计算模型，可能可以快速的解决一些尚未知道是否属于'''P'''的问题；但是，没有一个它们已知能够解决的问题是'''NP'''完全的。不过，必须注意到'''P'''和'''NP'''问题的'''定义'''是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子计算机算法獲发现能有效解决一个'''NP'''完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类'''P'''和'''NP'''相等的证明。


== P≠NP的觀點 ==
Most computer scientists believe that '''P'''&ne;'''NP'''. A key reason for this belief is that after decades of studying these problems, nobody has been able to find a polynomial-time algorithm for an NP-hard problem. Moreover, these algorithms were sought long before the concept of NP-completeness was even known ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = [[co-NP]] and P = [[PH (complexity)|PH]].
{{who|多数计算机科学家}}相信'''P'''≠'''NP'''<ref>{{cite web |title=P≠NP - 百度学术 |url=https://xueshu.baidu.com/s?wd=P%E2%89%A0NP&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_hit=1 |website=xueshu.baidu.com |accessdate=2024-05-12 |archive-date=2024-05-12 |archive-url=https://web.archive.org/web/20240512072429/https://xueshu.baidu.com/s?wd=P%E2%89%A0NP&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_hit=1 |dead-url=no }}</ref>。该信念的一个关键原因是经过数十年对这些问题的研究，没人能发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法（[[Karp的21个NP完全问题]]，在最早发现的一批中，有所有著名的已经存在的问题）。进一步，P=NP这样的结果会导致很多惊人结果，那些结果现在被相信不成立，如NP=[[反NP]]和P=[[PH (复杂度)|PH]]。


也有这样论证：问题难求解（P）但易验证（NP），这和我们日常经验相符。
It is also intuitively argued that the idea of problems that are hard to solve, but easy to verify the solutions for matches our own real-world experience.


从另一方面讲，某些研究者认为我们过于相信'''P'''≠'''NP'''，而应该也去寻找'''P'''='''NP'''的证明。例如，2002年有这声明：<ref name="poll">{{Cite journal|author=William I. Gasarch|title=The P=?NP poll.|journal=SIGACT News|volume=33|issue=2|pages=34–47|url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/1052796.1052804|format=PDF|accessdate=29 December 2008|date=June 2002|archive-date=2019-10-27|archive-url=https://web.archive.org/web/20191027015501/http://www.cs.umd.edu/~gasarch/papers/poll.pdf|dead-url=no}}</ref>
On the other hand, some researchers believe that we are overconfident in '''P''' &ne; '''NP''' and should explore proofs of '''P''' = '''NP''' as well. For example, in 2002 these statements were made: [http://www.cs.umd.edu/~gasarch/papers/poll.ps]
{{Cquote|倾向P≠NP的主要论据是在穷举搜索领域完全没有本质性进展。也就是说，以我的观点，这是一个很弱的论据。算法的空间非常大，而我们只是在开始探索的起点。……[[费马最后定理]]的解决也显示非常简单的问题可能只有用非常深刻的理论才能解决。|{{lang|en|Moshe Y. Vardi}}，[[莱斯大学]]}}
: The main argument in favor of P&ne;NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [ . . . ] The resolution of [[Fermat's Last Theorem]] also shows that very simply [sic] questions may be settled only by very deep theories.
{{Cquote|过分依赖某种投机的猜測不是规划研究的一个好导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。|{{lang|en|Anil Nerode}}，[[康奈尔大学]]}}
: &mdash; Moshe Vardi, [[Rice University]]
: Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
: &mdash; Anil Nerode, [[Cornell University]]


== 关于证明的难度的结果 ==
==Results about difficulty of proof==
虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题很难，但是还有一些形式化的结果证明为什么该问题可能很难解决。


最常引用的结果之一是设计[[神諭機器|神諭]]。假想你有部魔法机器可以解决单一问题，例如「判定某数是否质数」，這魔法機器可以瞬间解决这问题。我们的新问题是，若我们獲允许任意利用这机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，'''P'''='''NP'''和'''P'''≠'''NP'''二者都可以证明。这个结论带来的后果是，任何可以通过修改[[神諭機器|神諭]]来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在'''相对化'''）。
Although a million dollar prize and a huge amount of dedicated research with no substantial results is enough to show the problem is difficult, there have also been some formal results demonstrating why the problem might be difficult to solve.


如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决'''P'''='''NP'''问题。[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps]{{Wayback|url=http://www-2.cs.cmu.edu/~rudich/papers/natural.ps |date=20050327012812 }}这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。
One of the most frequently-cited is a result involving [[oracle machine|oracles]]. Imagine you have a magical machine that can solve only one problem, such as determining if a given number is prime, but can solve it instantly. Our new question is now, if we're allowed to use this machine as much as we want, are there problems we can verify in polynomial time that we can't solve in polynomial time? It turns out that, depending on the problem that the machine solves, it can be shown ''both'' that '''P''' = '''NP''' and '''P''' &ne; '''NP'''. The practical consequence of this is that any proof which can be modified to account for the existence of this magic machine cannot solve the problem. Unfortunately, most known methods and nearly all classical methods can be modified in such a way (we say they are ''relativizing'').


这实际上也是为什么'''NP'''完全问题有用的原因－若对于NP完全问题存在有一个多项式时间算法，或者没有这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决'''P'''='''NP'''问题。
As if this weren't bad enough, a 1993 result by Razborov and Rudich showed that, given a certain credible assumption, proofs that are "natural" in a certain sense cannot solve the '''P''' = '''NP''' problem.[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps] This demonstrated that some of the most seemingly-promising methods of the time were also unlikely to succeed. As more theorems of this kind are proved, a potential proof of the theorem has more and more traps to avoid.


== 多項式時間演算法 ==
This is actually another reason why NP-complete problems are useful: if a polynomial-time algorithm, or the lack of one, can be demonstrated for an NP-complete problem, this would solve the '''P''' = '''NP''' problem in a way which is not believed to be excluded by the above results.
沒人知道多項式時間演算法對於NP完全問題是否存在。但是如果這樣的演算法存在，我們已經知道其中的一些了！例如下面的算法正確地接受了一個NP完全語言，但是沒人知道通常它需要多久執行。它是一個多項式時間演算法[[當且僅當]]'''P'''='''NP'''。


-{}-
==Polynomial-time algorithms==
// 接受NP完全語言的一個算法子集和。
//
// 這是一個多項式時間算法當且僅當P=NP。
//
// “多項式時間”表示它在多項式時間內返回“是”，若
// 結果是“是”，否則永遠運行。
//
// 輸入：S = 一個自然數的有限集
// 輸出："是"如果某個S的子集加起來等於0。
// 否則，它永遠運行沒有輸出。
// 注意: "程序數P"是你將一個整數P寫為二進制，然後
// 將位元串考慮為一個程序。
// 每個可能的程序都可以這樣產生，
// 雖然多數什麼也不做因為有語法錯誤。
//
FOR N = 1...infinity
FOR P = 1...N
以S為輸入運行程序數P N步
IF程序輸出一個不同的整數的列表
AND所有整數都在S中
AND整數的和為0
THEN
OUTPUT "是"並 停機


若'''P'''='''NP'''，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
No one knows whether polynomial-time algorithms exist for NP-complete languages. But if such algorithms do exist, we already know some of them! For example, the following algorithm correctly accepts an NP-complete language, but no one knows how long it takes in general. This is a polynomial-time algorithm if and only if '''P''' = '''NP'''.


可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
// Algorithm that accepts the NP-complete language [[subset sum problem|SUBSET-SUM]].
//
// This is a polynomial-time algorithm if and only if P=NP.
//
// "Polynomial-time" means it returns "YES" in polynomial time when
// the answer should be "YES", and runs forever when it's "NO".
//
// Input: S = a finite set of integers
// Output: "YES" if any subset of S adds up to 0.
// Otherwise, it runs forever with no output.
// Note: "Program number P" is the program you get by
// writing the integer P in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.<br>
FOR N = 1...infinity
FOR P = 1...N
Run program number P for N steps with input S
IF the program outputs a list of distinct integers
AND the integers are all in S
AND the integers sum to 0<br>
THEN
OUTPUT "YES" and HALT


-{}-
If '''P''' = '''NP''', then this is a polynomial-time algorithm accepting an NP-Complete language. "Accepting" means it gives "YES" answers in polynomial time, but
IF程序輸出一個完整的數學證明
is allowed to run forever when the answer is "NO".
AND證明的每一步合法
AND結論是S確實有（或者沒有）一個和為0的子集
THEN
OUTPUT "是"（如果獲證實，就"不是"）並停機


== 逻辑表述 ==
Perhaps we want to "solve" the SUBSET-SUM problem, rather than just "accept" the SUBSET-SUM language. That means we want it to always halt and return a "YES" or "NO" answer. Does any algorithm exist that can provably do this in polynomial time? No one knows. But if such algorithms do exist, then we already know some of them! Just replace the IF statement in the above algorithm with this:
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用[[一阶逻辑]]加上[[最小不动点]]操作（实际上，这允许了递归函数的定义）来表达。类似，NP是可以用存在性[[二阶逻辑]]来表达—也就是，在关系、函数、和子集上排除了[[全称量词]]的二阶逻辑。[[多项式等级]]，[[PH (复杂度)|PH]]中的语言对应与所有的[[二阶逻辑]]。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”


== 花絮 ==
IF the program outputs a complete math proof
[[普林斯顿大学]]计算机系楼将[[二进制代码]]表述的“P=NP？”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。<ref>{{Cite web |url=https://www.cs.princeton.edu/general/images/csbricksjpg |title=https://www.cs.princeton.edu/general/images/csbricksjpg |accessdate=2018-10-04 |archive-date=2019-02-17 |archive-url=https://web.archive.org/web/20190217120638/https://www.cs.princeton.edu/general/images/csbricksjpg |dead-url=no }}</ref>
AND each step of the proof is legal
<ref>{{Cite web |url=https://www.cs.princeton.edu/general/bricks |title=https://www.cs.princeton.edu/general/bricks |accessdate=2018-10-04 |archive-date=2017-12-14 |archive-url=https://web.archive.org/web/20171214081659/http://www.cs.princeton.edu/general/bricks |dead-url=no }}</ref>
AND the conclusion is that S does (or does not) have a subset summing to 0
THEN
OUTPUT "YES" (or "NO" if that was proved) and HALT


[[康奈尔大学]]的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：<ref>{{Cite web |url=http://www.cs.cornell.edu/hubes/pnp.htm |title=http://www.cs.cornell.edu/hubes/pnp.htm |accessdate=2005-07-15 |archive-date=2005-09-27 |archive-url=https://web.archive.org/web/20050927204236/http://www.cs.cornell.edu/hubes/pnp.htm |dead-url=no }}</ref>
==Logical characterizations==
{{quote|
反证法。设P{{=}}NP。令y为一个P{{=}}NP的证明。证明y可以用一个合格的-{zh-cn:计算机;zh-tw:電腦}-科学家在多项式时间内验证，我们认定这样的科学家的存在性为真，但因为P{{=}}NP，该证明y可在多项式时间内由这样的科学家发现，但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。}}


==註釋 ==
The P=NP problem can be restated in terms of the expressibility of certain classes of logical statements. All languages in P can be expressed in [[first order logic]] with the addition of a [[least fixed point]] operator (effectively, this allows the definition of recursive functions). Similarly, NP is the set of languages expressible in existential [[second order logic]] &mdash; that is, second order logic restricted to exclude [[universal quantification]] over relations, functions, and subsets. The languages in the [[polynomial hierarchy]], [[PH (complexity)|PH]], correspond to all of [[second order logic]]. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages that first-order logic with least fixed point cannot?"
{{Reflist|2}}


==Trivia==
==参考文献==
{{refbegin}}
The [[Princeton University]] computer science building has the question "P=NP?" encoded in [[Binary and text files |binary]] in its brickwork on the top floor of the west side. If it is proven that P=NP, the bricks can easily be changed to encode "P=NP!". [http://www.princeton.edu/~taubetap/tours/handbook.pdf]
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page]{{Wayback|url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm |date=20050715082404 }}。Lists a number of incorrect solutions to the problem.
* A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. ''Automata, Languages, and Programming'', Springer LNCS 115 (1981) 278-293 and ''J. Comb. Th. A'' 31 (1981) 199-214.
* E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
* [[Neil Immerman]]。Languages Which Capture Complexity Classes. ''15th ACM STOC Symposium'', pp.347-354. 1983.
{{refend}}


==延伸閱讀==
Hubert Chen, PhD, of [[Cornell University]] offers this tongue-in-cheek proof that P does not equal NP: "<i>Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction.</i>"[http://www.cs.cornell.edu/hubes/pnp.htm]
{{refbegin|2}}
* {{cite journal| doi =10.1007/3-540-10843-2_23| year =1981| title =Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.| first1 =A. S.| last1 =Fraenkel| first2 =D.| last2 =Lichtenstein| journal =Lecture Notes in Computer Science| volume =| issue =| pages =278–293| url =http://www.pubzone.org/dblp/conf/icalp/FraenkelL81| format =| accessdate =| archive-date =2017-04-25| archive-url =https://web.archive.org/web/20170425031512/http://www.pubzone.org/dblp/conf/icalp/FraenkelL81| dead-url =yes}}
* {{cite book | last1 = Garey | first1 = Michael | last2 = Johnson | first2 = David | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | url = https://archive.org/details/computersintract0000gare | publisher = [[W. H. Freeman and Company]] | location = San Francisco | year = 1979 | isbn = 0-7167-1045-5 }}
* {{cite book | last = Goldreich | first = Oded | title = P, Np, and Np-Completeness | publisher = Cambridge University Press | location = Cambridge | year = 2010 | isbn = 978-0-521-12254-2 }} [http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html Online drafts]{{Wayback|url=http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html |date=20180123073733 }}
* {{Cite journal | last1 = Immerman | first1 = N. | title = Languages which capture complexity classes | pages = 760–778 | year = 1987 | journal = SIAM Journal on Computing | volume = 16 | issue = 4 | doi = 10.1137/0216051 | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936 | access-date = 2018-01-19 | archive-date = 2013-04-29 | archive-url = https://web.archive.org/web/20130429170532/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936 | dead-url = no }}
* {{cite book | last = Cormen | first = Thomas | title = [[Introduction to Algorithms]] | publisher = [[MIT Press]] | location = Cambridge | year = 2001 | isbn = 0-262-03293-7 }}
* {{cite book | last = Papadimitriou | first = Christos | title = Computational Complexity | url = https://archive.org/details/computationalcom0000papa | publisher = Addison-Wesley | location = Boston | year = 1994 | isbn = 0-201-53082-1 }}
* {{Cite journal | last1 = Fortnow | first1 = L. | doi = 10.1145/1562164.1562186 | title = The Status of the P versus NP problem | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78 | year = 2009 | url = http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext | pmid = | pmc = | access-date = 2018-01-19 | archive-date = 2017-02-15 | archive-url = https://web.archive.org/web/20170215201755/http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext | dead-url = no }}
* {{cite web | last1 = Fortnow | first1 = L. | last2 = Gasarch | first2 = W. | title = Computational complexity | url = http://weblog.fortnow.com | accessdate = 2019-04-27 | archive-date = 2009-05-01 | archive-url = https://web.archive.org/web/20090501175410/http://weblog.fortnow.com/ | dead-url = no }}
{{refend}}


==See also==
== 外部链接 ==
* [http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html 未來數學家的挑戰（P與NP的簡介，清楚明瞭）]{{Wayback|url=http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html |date=20061011151657 }}{{zh-hant}}
*[[P (complexity)]]
* [https://web.archive.org/web/20051126011639/http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
*[[NP (complexity)]]
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]{{Wayback|url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |date=20061206012118 }}
*[[NP-complete]]
* [https://web.archive.org/web/20050716082540/http://www.cse.iitk.ac.in/news/primality.html Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002]

* [https://web.archive.org/web/20050723210919/http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
==External links and references==
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]{{Wayback|url=http://www.complexityzoo.com/ |date=20081204193604 }}

* [http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page]. Lists a number of incorrect solutions to the problem.
* A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. ''Automata, Languages, and Programming'', Springer LNCS 115 (1981) 278-293 and ''J. Comb. Th. A'' 31 (1981) 199-214.
* E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
* [[Neil Immerman]]. Languages Which Capture Complexity Classes. ''15th ACM STOC Symposium'', pp.347-354. 1983.
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* [http://www.cse.iitk.ac.in/news/primality.html Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002]
* [http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]


== 参见 ==
{{ComplexityClasses}}
* [[P (复杂度)]]
* [[NP (复杂度)]]
* [[NP完全]]
* [[未解決的數學問題|未解決數學問題]]
* [[NP-complete問題列表]]
* [[幾乎完備]]（{{tsl|en|Almost complete|Almost complete}}）問題與[[弱完備]]（{{tsl|en|weakly complete|weakly complete}}）問題
* [[ASR-complete]]
* [[Ladner理論]]
* [[NP困难]]


{{-}}
[[Category:Complexity classes]]
{{复杂度类}}
[[Category:Conjectures]]
[[Category:Unsolved problems in mathematics]]


[[Category:複雜度類]]
[[de:P/NP-Problem]]
[[Category:猜想]]
[[en:Complexity classes P and NP]]
[[Category:数学中未解决的问题]]
[[fr:Complexité des classes P et NP]]
[[Category:千禧年大奖难题]]
[[he:P=NP]]
[[Category:计算机科学中未解决的问题]]
[[it:Classi di complessità P e NP]]
[[ja:P≠NP予想]]
[[ko:P-NP 문제]]
[[th:กลุ่มความซับซ้อน พี และ เอ็นพี]]

2024年10月6日 (日) 09:29的最新版本

未解決的計算機科學問題：如果一个问题的解可以快速检验正确性，那么这个问题一定可以快速求解吗？
千禧年大獎難題

P/NP问题是理论计算机科学中计算复杂度理论领域至今未解决的问题，是克雷数学研究所七題千禧年大奖难题之一。P/NP问题包括复杂度类P与NP的关系。1971年由史提芬·古克（Stephen A. Cook）和列昂尼德·列文（英语：Leonid Levin）分別提出。

P=NP

[编辑]

复杂度类P即為所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证它的解是否正確的决定问题组成，或者等效的说，那些可以在非確定型圖靈機上在多项式时间内找出解的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：

P和NP相等

在2002年对于100研究者的调查中，61人相信答案是否定的，9人相信答案是肯定的，22人不确定，而8人相信问题可能和现在所接受的公理独立，所以不可能证明或证否。[1]对于正确的解答，有一个一百萬美元的奖励。

NP-完全问题（或者叫NPC）的集合在这讨论有重大作用，它们可以大致的描述为那些在NP中最不像在P中的（确切定义细节请参看NP-完全理论）。计算机科学家现在相信P、NP和NPC类之间的关系如图中所示，其中P和NPC类不相交。

假设P≠NP的复杂度类的图解。如P=NP则三个类相同。

簡單來說，P=NP即：「若问题的答案可以很快验证，其答案是否也可以很快被计算出來。」

例如某大数是否合数：如53308290611有否非平凡因數。答案是肯定的，虽然人手找出一个因數很麻烦。从另一个方面讲，如果有人声称答案是「对，224737可以整除53308290611」，则我们可以很快用除法验证。验证一个数是除数比找出一個明顯除数来简单得多。用於验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定正确的证明，问题的正面答案可以很快（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。

虽然这个特定的问题，最近也獲证實在P类中（参看下面的关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类P。

像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP=FNP）是等价的。

学术定义

[编辑]

更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。

现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多nk步内产生“是／否”答案（其中n是w的长度而k不依赖于w）。然後假设：w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。 则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。）

NP完全

[编辑]

要解决P=NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行推销员问题的判定问题版本为NP完全。所以NP中的任何问题的任何特例可以在多项式时间内转换成旅行商问题的一个特例。所以若旅行商问题能证實在P内，则P=NP。旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P=NP。不幸的是，虽然很多重要的问题被证實为NP完全，但却没有一个有已知快速的算法。

更难的问题

[编辑]

虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是NP困难的。因为可以证明P≠EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定皮尔斯伯格算术（英语：Presburger arithmetic）中的命题是否为真的问题更加困难。Fischer和Rabin（英语：Michael O. Rabin）于1974年证明每个决定Presburger命题的真伪性的算法有最少22cn的运行时间，c为某个常数。这裡，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题，而它们无法在任何给定时间内解决。

P真的容易处理吗？

[编辑]

上面所有的讨论，假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：

  • 它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是指数时间的），但是对于n取值直到几千时还是很容易处理的。
  • 它忽略了指数的大小。一个时间复杂度n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间层次定理）。一个时间复杂度2n/1000的问题不属于P，但对于n直到几千还是容易应对的。
  • 它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
  • 它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP，BPP）。
  • 新的诸如量子计算机这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子计算机算法獲发现能有效解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。

P≠NP的觀點

[编辑]

多数计算机科学家[谁？]相信P≠NP[2]。该信念的一个关键原因是经过数十年对这些问题的研究，没人能发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步，P=NP这样的结果会导致很多惊人结果，那些结果现在被相信不成立，如NP=反NP和P=PH。

也有这样论证：问题难求解（P）但易验证（NP），这和我们日常经验相符。

从另一方面讲，某些研究者认为我们过于相信P≠NP，而应该也去寻找P=NP的证明。例如，2002年有这声明：[3]

关于证明的难度的结果

[编辑]

虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题很难，但是还有一些形式化的结果证明为什么该问题可能很难解决。

最常引用的结果之一是设计神諭。假想你有部魔法机器可以解决单一问题，例如「判定某数是否质数」，這魔法機器可以瞬间解决这问题。我们的新问题是，若我们獲允许任意利用这机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P=NP和P≠NP二者都可以证明。这个结论带来的后果是，任何可以通过修改神諭来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。

如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P=NP问题。[1]（页面存档备份，存于互联网档案馆）这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。

这实际上也是为什么NP完全问题有用的原因－若对于NP完全问题存在有一个多项式时间算法，或者没有这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决P=NP问题。

多項式時間演算法

[编辑]

沒人知道多項式時間演算法對於NP完全問題是否存在。但是如果這樣的演算法存在，我們已經知道其中的一些了！例如下面的算法正確地接受了一個NP完全語言，但是沒人知道通常它需要多久執行。它是一個多項式時間演算法當且僅當P=NP。 

  // 接受NP完全語言的一個算法子集和。
  //
  // 這是一個多項式時間算法當且僅當P=NP。
  //
  // “多項式時間”表示它在多項式時間內返回“是”，若
  // 結果是“是”，否則永遠運行。
  //
  // 輸入：S = 一個自然數的有限集
  // 輸出："是"如果某個S的子集加起來等於0。
  //         否則，它永遠運行沒有輸出。
  // 注意:  "程序數P"是你將一個整數P寫為二進制，然後
  //         將位元串考慮為一個程序。
  //         每個可能的程序都可以這樣產生，
  //         雖然多數什麼也不做因為有語法錯誤。
  //         
  FOR N = 1...infinity
      FOR P = 1...N
          以S為輸入運行程序數P N步
          IF程序輸出一個不同的整數的列表
              AND所有整數都在S中
              AND整數的和為0
          THEN
              OUTPUT "是"並 停機

若P=NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。

可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句： 

          IF程序輸出一個完整的數學證明
              AND證明的每一步合法
              AND結論是S確實有（或者沒有）一個和為0的子集
          THEN
              OUTPUT "是"（如果獲證實，就"不是"）並停機

逻辑表述

[编辑]

P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似，NP是可以用存在性二阶逻辑来表达—也就是，在关系、函数、和子集上排除了全称量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”

花絮

[编辑]

普林斯顿大学计算机系楼将二进制代码表述的“P=NP？”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[4] [5]

康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：[6]

反证法。设P=NP。令y为一个P=NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真，但因为P=NP，该证明y可在多项式时间内由这样的科学家发现，但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。

註釋

[编辑]
  1. ^ Wayback Machine（网页存档）. web.archive.org. 2005-04-04 [2017-09-05]. （原始内容存档于2005-04-04）. 
  2. ^ P≠NP - 百度学术. xueshu.baidu.com. [2024-05-12]. （原始内容存档于2024-05-12）. 
  3. ^ William I. Gasarch. The P=?NP poll. (PDF). SIGACT News. June 2002, 33 (2): 34–47 [29 December 2008]. doi:10.1145/1052796.1052804. （原始内容存档 (PDF)于2019-10-27）. 
  4. ^ https://www.cs.princeton.edu/general/images/csbricksjpg. [2018-10-04]. （原始内容存档于2019-02-17）.  外部链接存在于|title= (帮助)
  5. ^ https://www.cs.princeton.edu/general/bricks. [2018-10-04]. （原始内容存档于2017-12-14）.  外部链接存在于|title= (帮助)
  6. ^ http://www.cs.cornell.edu/hubes/pnp.htm. [2005-07-15]. （原始内容存档于2005-09-27）.  外部链接存在于|title= (帮助)

参考文献

[编辑]
  • Gerhard J. Woeginger. The P-versus-NP page（页面存档备份，存于互联网档案馆）。Lists a number of incorrect solutions to the problem.
  • A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
  • E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
  • Neil Immerman。Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347-354. 1983.

延伸閱讀

[编辑]

外部链接

[编辑]

参见

[编辑]
检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=P/NP问题&oldid=84483763”