更改

==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 ''?''.<ref name="Official Problem Description" /> 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>{{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 ''?''.<ref name="Official Problem Description" /> 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 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吗？。根据民意调查的结果，大多数计算机科学家认为P≠ NP。这种观点的一个主要原因是，经过几十年对这些问题的研究，没有人能够为已知的3000多个重要NP完全问题找到任何一个多项式时间算法（参见NP完全问题列表）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，Karp的21个问题是非常知名的）。此外，P=NP这个结论意味着许多其他惊人的结论，这些结论目前被认为是错误的，例如NP=co-NP和P=PH。

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

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题的存在符合现实世界的经验。<blockquote>如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方案之间没有根本的差距。

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

— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）

— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）

</blockquote>

</blockquote>

另一方面，一些研究人员认为，人们过于相信P≠ NP了，研究人员也应该探索P=NP的证明。例如，2002年有如下观点：

另一方面，一些研究人员认为，人们过于相信P ≠ NP了，研究人员也应该探索P = NP的证明。例如，2002年有如下观点：

<blockquote>支持P≠ NP主要是在穷举搜索领域缺乏重大进展。在我看来，这是一个非常薄弱的论点。算法的空间非常大，我们才刚刚开始探索。[...] 费马最后定理的解决也表明，非常简单的问题只能通过非常深刻的理论来解决。

<blockquote>支持P ≠ NP主要是因为在穷举搜索领域缺乏重大进展。在我看来，这是一个非常薄弱的论点。算法的搜索空间非常大，我们才刚刚开始探索。[...] 费马最后定理的证明也表明，非常简单的问题只能通过非常深刻的理论来解决。<ref name="poll" />

— 莫斯·Y·瓦迪，莱斯大学（Moshe Y. Vardi, Rice University）

— 莫斯·Y·瓦迪，莱斯大学（Moshe Y. Vardi, Rice University）

— 安尼尔·内罗德，康奈尔大学（Anil Nerode, Cornell University）</blockquote>

— 安尼尔·内罗德，康奈尔大学（Anil Nerode, Cornell University）</blockquote>

An example of a field that could be upended by a solution showing P = NP is [[cryptography]], which relies on certain problems being difficult. A constructive and efficient solution<ref group="Note">Exactly how efficient a solution must be to pose a threat to cryptography depends on the details.  A solution of <math>O(N^2)</math> with a reasonable constant term would be disastrous.  On the other hand, a solution that is <math>\Omega(N^4)</math> in almost all cases would not pose an immediate practical danger.</ref> to an NP-complete problem such as [[Boolean satisfiability problem#3-satisfiability|3-SAT]] would break most existing cryptosystems including:

An example of a field that could be upended by a solution showing P = NP is [[cryptography]], which relies on certain problems being difficult. A constructive and efficient solution<ref group="Note">Exactly how efficient a solution must be to pose a threat to cryptography depends on the details.  A solution of <math>O(N^2)</math> with a reasonable constant term would be disastrous.  On the other hand, a solution that is <math>\Omega(N^4)</math> in almost all cases would not pose an immediate practical danger.</ref> to an NP-complete problem such as [[Boolean satisfiability problem#3-satisfiability|3-SAT]] would break most existing cryptosystems including:

* Existing implementations of [[public-key cryptography]],<ref>See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997

* Existing implementations of [[public-key cryptography]],<ref name=":25">See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997

|publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} for a reduction of factoring to SAT.  A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.

|publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} for a reduction of factoring to SAT.  A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.

*[[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref>See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F.  |author2=Marraro, L.  |name-list-style=amp |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |citeseerx=10.1.1.104.962 |doi=10.1023/A:1006326723002|s2cid=3114247 }} in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses.  A 3DES problem instance would be about 3 times this size.</ref> used for the encryption of communications data.

*[[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref>See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F.  |author2=Marraro, L.  |name-list-style=amp |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |citeseerx=10.1.1.104.962 |doi=10.1023/A:1006326723002|s2cid=3114247 }} in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses.  A 3DES problem instance would be about 3 times this size.</ref> used for the encryption of communications data.