更改

==认为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" />大多数计算机科学家认为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" /><ref>Rosenberger, Jack (May 2012). [http://mags.acm.org/communications/201205?pg=12 "P vs. NP poll results"]. ''Communications of the ACM''. '''55''' (5): 10.</ref>大多数计算机科学家认为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，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。

另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；<ref name="Berger" />如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。

另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；<ref name="Berger" />如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref>History of this letter and its translation from Michael Sipser. [["The History and Status of the P versus NP question"]]</ref><ref>David S. Johnson (2012). [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 "A Brief History of NP-Completeness, 1954–2012"]. [[wikipedia:CiteSeerX_(identifier)|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 10.1.1.399.1480]. From pages 359–376 of Optimization Stories, [[wikipedia:Martin_Grötschel|M. Grötschel]] (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.</ref><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem''）''是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_=_NP|该节]]】</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<ref name="Official Problem Description" /><blockquote>... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。</blockquote>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：<ref>History of this letter and its translation from Michael Sipser. [http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf "The History and Status of the P versus NP question"] (PDF).</ref><ref>David S. Johnson (2012). [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 "A Brief History of NP-Completeness, 1954–2012"]. [[wikipedia:CiteSeerX_(identifier)|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 10.1.1.399.1480]. From pages 359–376 of Optimization Stories, [[wikipedia:Martin_Grötschel|M. Grötschel]] (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.</ref><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem''）''是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。</u>【没看懂，[[wikipedia:P_versus_NP_problem#P_=_NP|该节]]】</blockquote>类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说<ref name="Official Problem Description" /><blockquote>... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。</blockquote>数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。

唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":30" /><blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n^M位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>

唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":30" /><blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n^M位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>