134
个编辑
更改
跳到导航
跳到搜索
第356行：
第356行： − − But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:<ref>History of this letter and its translation from {{cite web |title=The History and Status of the P versus NP question |author=Michael Sipser |url=http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf}}</ref><ref>{{cite document |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.399.1480 |title=A Brief History of NP-Completeness, 1954–2012 |author=David S. Johnson|year=2012 |citeseerx=10.1.1.399.1480 }} From pages 359–376 of Optimization Stories, [[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> − {{quote|If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n<sup>2</sup>), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the [[Entscheidungsproblem]], the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem.}} − Similarly, [[Stephen Cook]] (assuming not only a proof, but a practically efficient algorithm) says<ref name="Official Problem Description">{{Cite journal|last=Cook|first=Stephen|author-link=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]] |date=April 2000 |url=http://www.claymath.org/sites/default/files/pvsnp.pdf |access-date=18 October 2006}}</ref> 第422行：
第418行： − +
→P = NP
另一方面，如果将许多目前在数学上难以处理的问题变得易于处理，将会产生巨大的积极影响。例如，运筹学中的许多问题都是 np 完全问题，比如某些类型的整数规划和旅行推销员问题。这些问题的有效解决方案将对物流产生巨大的影响。许多其他重要问题，如蛋白质结构预测中的一些问题，也是 np 完全问题; 如果这些问题能够有效地解决，它将促进生命科学和生物技术的相当大的进步。
另一方面，如果将许多目前在数学上难以处理的问题变得易于处理，将会产生巨大的积极影响。例如，运筹学中的许多问题都是 np 完全问题，比如某些类型的整数规划和旅行推销员问题。这些问题的有效解决方案将对物流产生巨大的影响。许多其他重要问题，如蛋白质结构预测中的一些问题，也是 np 完全问题; 如果这些问题能够有效地解决，它将促进生命科学和生物技术的相当大的进步。
But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:History of this letter and its translation from From pages 359–376 of Optimization Stories, 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.
But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:History of this letter and its translation from From pages 359–376 of Optimization Stories, 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.
另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是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><blockquote><u>如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n<sup>2</sup>），这将产生重大影响。也就是说，这意味着，尽管决策问题（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. [["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<sup>2</sup>），这将产生重大影响。也就是说，这意味着，尽管决策问题（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<sup>M</sup>位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>
唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：<ref name=":30" /><blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n<sup>M</sup>位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。</blockquote>