更改

==Reasons to believe P ≠ NP or P = NP ==

==Reasons to believe P ≠ NP or P = NP ==

Cook provides a restatement of the problem in <small>THE P VERSUS NP PROBLEM</small> as: ''Does'' P = NP ''?''.According to polls,<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref name=":24">{{cite journal|title=P vs. NP poll results|journal=Communications of the ACM|date=May 2012|volume=55|issue=5|page=10|first=Jack|last=Rosenberger|url=http://mags.acm.org/communications/201205?pg=12}}</ref> most computer scientists believe that P&nbsp;≠&nbsp;NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see [[List of NP-complete problems]]). These algorithms were sought long before the concept of NP-completeness was even defined ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems at the time they were shown to be NP-complete). 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]].

Cook provides a restatement of the problem in <small>THE P VERSUS NP PROBLEM</small> as: ''Does'' P = NP ''?''.According to polls,<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref>most computer scientists believe that P&nbsp;≠&nbsp;NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see [[List of NP-complete problems]]). These algorithms were sought long before the concept of NP-completeness was even defined ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems at the time they were shown to be NP-complete). 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]].

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?. According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). 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.

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?. According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). 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.

==认为P ≠ NP 或 P = NP的原因==

==认为P ≠ NP 或 P = NP的原因==

库克将P与NP问题重述为：P = NP吗？<ref name=":35">[[wikipedia:Stephen_Cook|Cook, Stephen]] (April 2000). [http://www.claymath.org/sites/default/files/pvsnp.pdf "The P versus NP Problem"] (PDF). [[wikipedia:Clay_Mathematics_Institute|Clay Mathematics Institute]]. Retrieved 18 October 2006.</ref>根据民意调查的结果，<ref name="poll" /><ref name=":35" />大多数计算机科学家认为P ≠ NP。这种观点的一个主要原因是，经过对这些问题几十年的研究，没有人能够为已知的3000多个重要的NP完全问题找到任何一种多项式时间算法（参见[[wikipedia:List_of_NP-complete_problems|NP完全问题列表]]）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，卡普（Karp）的21个问题是当时非常知名的NP问题）。此外，P = NP这个结论意味着许多其他惊人的结论，而这些结论目前被认为是错误的，例如NP = co-NP和P = PH。

库克将P与NP问题重述为：P = NP吗？<ref name=":35">[[wikipedia:Stephen_Cook|Cook, Stephen]] (April 2000). [http://www.claymath.org/sites/default/files/pvsnp.pdf "The P versus NP Problem"] (PDF). [[wikipedia:Clay_Mathematics_Institute|Clay Mathematics Institute]]. Retrieved 18 October 2006.</ref>根据民意调查的结果，<ref name="poll" />大多数计算机科学家认为P ≠ NP。这种观点的一个主要原因是，经过对这些问题几十年的研究，没有人能够为已知的3000多个重要的NP完全问题找到任何一种多项式时间算法（参见[[wikipedia:List_of_NP-complete_problems|NP完全问题列表]]）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，卡普（Karp）的21个问题是当时非常知名的NP问题）。此外，P = NP这个结论意味着许多其他惊人的结论，而这些结论目前被认为是错误的，例如NP = co-NP和P = PH。

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题，它们的存在与现实世界的经验相符。<ref>Scott Aaronson. [http://scottaaronson.com/blog/?p=122 "Reasons to believe"]., point 9.</ref><blockquote>如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题，它们的存在与现实世界的经验相符。<ref>Scott Aaronson. [http://scottaaronson.com/blog/?p=122 "Reasons to believe"]., point 9.</ref><blockquote>如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。