4
个编辑
更改
跳到导航
跳到搜索
第12行：
第12行： − + 第18行：
第18行： − 上面使用的非正式术语 quickly，意思是存在一个用多项式时间完成任务的算法，这样完成任务的时间随着算法输入大小的多项式函数而变化(而不是，比如说，EXPTIME)。一般的问题类别，其中一些算法可以提供一个答案在多项式时间是“ p”或“类别 p”。对于某些问题，没有已知的快速找到答案的方法，但是如果一个人得到了显示答案是什么的信息，那么快速验证答案是可能的。一类问题的答案可以在多项式时间内得到验证，这类问题是 NP，即“ NP”。不确定的图灵机可以移动到不由以前的状态确定的状态。这样的机器可以在多项式时间内解决一个 NP 问题，通过进入正确的答案状态(靠运气) ，然后传统地验证它。这种机器不能用来解决实际问题，但可以用作理论模型。+ 第24行：
第24行： − 一个 p 与 NP 问题的答案将决定可以在多项式时间内验证的问题是否也可以在多项式时间内解决。如果事实证明 p ≠ NP，这被广泛认为，这将意味着在 NP 中有一些问题是难以计算而难以验证的: 他们不能在多项式时间内解决，但答案可以在多项式时间内验证。+ 第30行：
第30行： − 这个问题被许多人认为是计算机科学中最重要的公开问题。除了是计算理论中的一个重要问题外，无论哪种证明都将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学和许多其他领域产生深远的影响。+ − − 它是由千禧年大奖难题克雷数学研究所选出的7个最佳解决方案之一，每个方案的第一个正确解决方案将获得100万美元的奖金。 第48行：
第46行： − 考虑数独，一个游戏，其中玩家被给予一个部分填充的数字网格，并试图完成网格遵循一定的规则。给定一个不完整的数独网格，任何大小，是否至少有一个合法的解决方案？任何提出的解决方案都很容易验证，而且随着网格的增大，检查解决方案的时间增长缓慢(多项式)。然而，所有已知的算法寻找解决方案，为困难的例子，时间成指数增长的网格变得更大。因此，数独是 NP (快速检查) ，但似乎不是在 p (快速解决)。成千上万的其他问题看起来很相似，它们检查起来很快，但解决起来却很慢。研究人员已经表明，NP 中的许多问题都有一个额外的特性，即任何一个问题的快速解都可以用来快速解决 NP 中的任何其他问题，这个特性称为 NP 完全性。几十年的研究并没有找到这些问题的快速解决方案，所以大多数科学家怀疑这些问题都不能很快解决。然而，这一点从未得到证实。+ 第60行：
第58行： − 1971年，Stephen Cook 在他的开创性论文《定理证明过程的复杂性》中提出了 P/NP问题的精确陈述(1973年由 Leonid Levin 独立撰写)。+ 第66行：
第64行： − 虽然 P/NP问题在1971年被正式定义，但是之前已经有人暗示了这个问题，证明的困难，以及潜在的后果。1955年，数学家约翰 · 纳什给美国国家安全局写了一封信，推测破解一个足够复杂的密码需要密钥长度呈指数增长。如果证明了这一点(纳什也表示了适当的怀疑) ，那么这就意味着 p ≠ NP，因为提出的密钥可以在多项式时间内很容易地得到验证。1956年 Kurt g ö del 写给约翰·冯·诺伊曼的信中提到了这个潜在的问题。哥德尔询问定理证明(现在已知为 co-np 完全)是否可以在二次时间或线性时间内解决，并指出最重要的结果之一ーー如果可以，那么数学证明的发现就可以自动化。+ 第96行：
第94行： − + 第198行：
第196行： − + 第320行：
第318行： − +
前三段内容修改
The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
P/NP问题是计算机科学中一个尚未解决的主要问题。它要求每一个问题的解决方案能够被快速验证，是否也能被快速解决。
P/NP问题是众多尚未解决的计算机理论和算法复杂度中最重要的一个难题，分别由加拿大科学家史蒂芬·库克和俄罗斯科学家雷纳德·里文在1970年代独立提出。它也被克雷数学研究所列为“七大千禧大奖难题”之一，第一个解决的人将100万美元奖励。
The informal term ''quickly'', used above, means the existence of an algorithm solving the task that runs in [[polynomial time]], such that the time to complete the task varies as a [[polynomial function]] on the size of the input to the algorithm (as opposed to, say, [[exponential time]]). The general class of questions for which some [[algorithm]] can provide an answer in polynomial time is "[[P (complexity)|'''P''']]" or "'''class P'''". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be ''verified'' in polynomial time is [[NP (complexity)|'''NP''']], which stands for "nondeterministic polynomial time".<ref group="Note">A [[nondeterministic Turing machine]] can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.</ref>
The informal term ''quickly'', used above, means the existence of an algorithm solving the task that runs in [[polynomial time]], such that the time to complete the task varies as a [[polynomial function]] on the size of the input to the algorithm (as opposed to, say, [[exponential time]]). The general class of questions for which some [[algorithm]] can provide an answer in polynomial time is "[[P (complexity)|'''P''']]" or "'''class P'''". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be ''verified'' in polynomial time is [[NP (complexity)|'''NP''']], which stands for "nondeterministic polynomial time".<ref group="Note">A [[nondeterministic Turing machine]] can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.</ref>
The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.
The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.
P/NP问题的核心在于判断一个计算问题能否被快速的解决和答案可被快速的验证。前面的“快速”指是否存在一个只用'''多项式时间'''内解决计算问题的算法，也就是说算法完成计算任务的时间与任务的输入量呈多项式函数相关，而不是线形时间或指数时间。复杂度P类是指一类可以通过多项式时间内的算法解决的计算问题。还有一类计算问题，它们没有已知的可以在多项式时间内解决的算法，但可以在多项式时间内快速验证答案是可能的，这类计算问题即复杂度NP类问题。如果从以图灵机来理解，一个非确定型图灵机因其不受以往确定状态的影响，可以在多项式时间内随机移动到NP类问题的答案态，再通过传统方式验证它。那么这种机器只可以用作理论模型，但没有用它解决实际问题的价值。
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
P/NP问题的答案将决定可在多项式时间内验证的计算问题是否也可以在多项式时间内解决。当前，科学家广泛认为P ≠ NP，若它被证明，将意味着在NP类计算问题中有一些问题是难以通过算法计算的。也就是说，他们不能在多项式时间内解决，但答案可以在多项式时间内验证。简单的来说，P ≠ NP代表部分问题是“困难”的，反之，如果P = NP则意味着所有计算问题都会“容易”解决。
The problem is considered by many to be the most important open problem in [[computer science]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | author-link = Lance Fortnow | year = 2009 | title = The status of the P versus NP problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | citeseerx = 10.1.1.156.767 | s2cid = 5969255 | access-date = 26 January 2010 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24 February 2011 | url-status = dead }}</ref> Aside from being an important problem in [[computational theory]], a proof either way would have profound implications for mathematics, [[cryptography]], algorithm research, [[artificial intelligence]], [[game theory]], multimedia processing, [[philosophy]], [[economics]] and many other fields.<ref>{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=9780691156491|location=Princeton, NJ}}</ref>
The problem is considered by many to be the most important open problem in [[computer science]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | author-link = Lance Fortnow | year = 2009 | title = The status of the P versus NP problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | citeseerx = 10.1.1.156.767 | s2cid = 5969255 | access-date = 26 January 2010 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24 February 2011 | url-status = dead }}</ref> Aside from being an important problem in [[computational theory]], a proof either way would have profound implications for mathematics, [[cryptography]], algorithm research, [[artificial intelligence]], [[game theory]], multimedia processing, [[philosophy]], [[economics]] and many other fields.<ref>{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=9780691156491|location=Princeton, NJ}}</ref>
The problem is considered by many to be the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.
The problem is considered by many to be the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.
科学家们广泛认为P/NP问题是计算机科学中最重要的问题，而且这个问题的证明都将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学和许多其他领域产生深远的影响。
It is one of the seven [[Millennium Prize Problems]] selected by the [[Clay Mathematics Institute]], each of which carries a US$1,000,000 prize for the first correct solution.
It is one of the seven [[Millennium Prize Problems]] selected by the [[Clay Mathematics Institute]], each of which carries a US$1,000,000 prize for the first correct solution.
It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.
It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.
== Example ==
== Example ==
Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable). Thousands of other problems seem similar, in that they are fast to check but slow to solve. Researchers have shown that many of the problems in NP have the extra property that a fast solution to any one of them could be used to build a quick solution to any other problem in NP, a property called NP-completeness. Decades of searching have not yielded a fast solution to any of these problems, so most scientists suspect that none of these problems can be solved quickly. This, however, has never been proven.
Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable). Thousands of other problems seem similar, in that they are fast to check but slow to solve. Researchers have shown that many of the problems in NP have the extra property that a fast solution to any one of them could be used to build a quick solution to any other problem in NP, a property called NP-completeness. Decades of searching have not yielded a fast solution to any of these problems, so most scientists suspect that none of these problems can be solved quickly. This, however, has never been proven.
我们在此以数独为例以理解以上的概念。在数独当中，玩家会获得一个部分填充的数字网格，玩家按照一定的规则完成网格中剩余的数字则算胜利。问题是，已知一个任意大小的数字网格，我们如何知道网格至少有一个满足规则的填写答案？在此，如果我们给定任意的填写答案都很容易验证，且随着网格的增大，检查答案的呈多项式时间增长。但是反过来，如果我们想要通过算法寻找解决答案，随网格变大，却需要指数性时间的增长。因此，我们认为数独是一个典型的NP问题，即答案可快速验证，但不太能快速解决。世界上有很多问题看起来跟数独很相似，它们检查起来很快，但解决起来却很慢。不过，科学家发现，NP类问题中的许多计算问题都有一个特性，即任何一个问题的快速解都可以帮助解决NP类中的任何其他问题，这个特性称为'''NP完全性（英文：NP- Completeness）'''。由于我们暂未找到这些NP完全性问题的快速解，所以大多数科学家怀疑这类问题不可能找到快速解。
==History==
==History==
The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" (and independently by Leonid Levin in 1973).
The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" (and independently by Leonid Levin in 1973).
1971年，多伦多大学教授史蒂芬·库克在他的开创性论文《定理证明过程的复杂性》（英文："The complexity of theorem proving procedures"）中提出了P/NP问题的精确陈述，这个问题后来又在1973年由波士顿大学教授雷纳德·里文独立提出。
Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician [[John Forbes Nash Jr.|John Nash]] wrote a letter to the [[National Security Agency|NSA]], where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key.<ref>{{cite web |title=Letters from John Nash |url=https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf |author=NSA |year=2012}}</ref> If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. Gödel asked whether theorem-proving (now known to be [[co-NP-complete]]) could be solved in [[quadratic time|quadratic]] or [[linear time]],<ref>{{cite journal | last1 = Hartmanis | first1 = Juris | title = Gödel, von Neumann, and the P = NP problem | url = http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf | journal = Bulletin of the European Association for Theoretical Computer Science | volume = 38 | pages = 101–107 }}</ref> and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.
Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician [[John Forbes Nash Jr.|John Nash]] wrote a letter to the [[National Security Agency|NSA]], where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key.<ref>{{cite web |title=Letters from John Nash |url=https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf |author=NSA |year=2012}}</ref> If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. Gödel asked whether theorem-proving (now known to be [[co-NP-complete]]) could be solved in [[quadratic time|quadratic]] or [[linear time]],<ref>{{cite journal | last1 = Hartmanis | first1 = Juris | title = Gödel, von Neumann, and the P = NP problem | url = http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf | journal = Bulletin of the European Association for Theoretical Computer Science | volume = 38 | pages = 101–107 }}</ref> and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.
Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician John Nash wrote a letter to the NSA, where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key. If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.
Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician John Nash wrote a letter to the NSA, where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key. If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.
虽然P/NP问题在1971年才被正式定义，但是之前已经有人了想到了这个问题、证明的难度和潜在的后果。1955年，数学家约翰·纳什给美国国家安全局写了一封信，他推测破解一个足够复杂的密码需要密钥长度呈指数增长。如果有人能证明这一点，那么这就意味着P ≠ NP，因为任意的密钥解可以在多项式时间得到验证。1956年，库尔特·哥德尔在写给约翰·冯·诺伊曼的信中提到了这个问题。哥德尔想要知道定理证明（现在被定义为co-NP完全问题）是否可以在二次时间或线性时间内解决，如果是的话，寻找定理的数学证明过程将可以自动化。（翻译到此）
==Context==
==Context==
==NP-completeness==
==NP-completeness==
[[File:P np np-complete np-hard.svg|thumb|300px|right|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)]]
[[File:P np np-complete np-hard.svg|thumb|300px|right|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)|链接=Special:FilePath/P_np_np-complete_np-hard.svg]]
{{Main article|NP-completeness}}
{{Main article|NP-completeness}}
To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
==Does P mean "easy"?==
==Does P mean "easy"?==
[[File:KnapsackEmpComplexity.GIF|thumb|310 px|The graph shows the running time vs. problem size for a [[knapsack problem]] of a state-of-the-art, specialized algorithm. The [[Curve fitting|quadratic fit]] suggests that the algorithmic complexity of the problem is O((log(''n''))<sup>2</sup>).<ref name=Pisinger2003>Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark</ref>]]
[[File:KnapsackEmpComplexity.GIF|thumb|310 px|The graph shows the running time vs. problem size for a [[knapsack problem]] of a state-of-the-art, specialized algorithm. The [[Curve fitting|quadratic fit]] suggests that the algorithmic complexity of the problem is O((log(''n''))<sup>2</sup>).<ref name=Pisinger2003>Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark</ref>|链接=Special:FilePath/KnapsackEmpComplexity.GIF]]
All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as ''[[Cobham's thesis]]''. It is a common and reasonably accurate {{citation needed|reason=Accurate in what way, according to whom?|date=January 2021}} assumption in complexity theory; however, it has some caveats.
All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as ''[[Cobham's thesis]]''. It is a common and reasonably accurate {{citation needed|reason=Accurate in what way, according to whom?|date=January 2021}} assumption in complexity theory; however, it has some caveats.
[[Donald Knuth]] has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:<ref>{{cite book|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a|title=Twenty Questions for Donald Knuth|date=20 May 2014|work=informit.com|publisher=[[InformIT (publisher)|InformIT]]|last=Knuth|first=Donald E.|author-link=Donald Knuth|access-date=20 July 2014}}</ref>
[[Donald Knuth]] has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:<ref>{{cite book|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a|title=Twenty Questions for Donald Knuth|date=20 May 2014|work=informit.com|publisher=[[InformIT (publisher)|InformIT]]|last=Knuth|first=Donald E.|author-link=Donald Knuth|access-date=20 July 2014}}</ref>
{{quote|1=[...] if you imagine a number M that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do n<sup>M</sup> bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
<nowiki>{{quote|1=[...] if you imagine a number M that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do n</nowiki><sup>M</sup> bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:
Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof: