更改

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完全问题）是否可以在二次时间或线性时间内解决，如果是的话，寻找定理的数学证明过程将可以自动化。（翻译到此）

虽然P/NP问题在1971年才被正式定义，但是之前已经有人了想到了这个问题、证明的难度和潜在的后果。1955年，数学家约翰·纳什给美国国家安全局写了一封信，他推测破解一个足够复杂的密码需要密钥长度呈指数增长。如果有人能证明这一点，那么这就意味着P ≠ NP，因为任意的密钥解可以在多项式时间得到验证。1956年，库尔特·哥德尔在写给约翰·冯·诺伊曼的信中提到了这个问题。哥德尔想要知道定理证明（现在被定义为co-NP完全问题）是否可以在二次时间或线性时间内解决，如果是的话，寻找定理的数学证明过程将可以自动化。

==Context==

==Context==

<small>Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a [https://wiki.swarma.org/index.php/Turing_machine Turing machine] ''M'' guaranteed to halt in polynomial time, does there exist a polynomial-size input that ''M'' will accept?<ref name="Scott">{{Cite web|author=Scott Aaronson|title=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html |access-date=27 August 2007}}</ref> It is in NP because (given an input) it is simple to check whether ''M'' accepts the input by simulating ''M''; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine ''M'' that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.  Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.</small>   

<small>Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a [https://wiki.swarma.org/index.php/Turing_machine Turing machine] ''M'' guaranteed to halt in polynomial time, does there exist a polynomial-size input that ''M'' will accept?<ref name="Scott">{{Cite web|author=Scott Aaronson|title=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html |access-date=27 August 2007}}</ref> It is in NP because (given an input) it is simple to check whether ''M'' accepts the input by simulating ''M''; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine ''M'' that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.  Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.</small>   

<small>其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。（翻译到此）</small>

<small>其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。</small>

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713&ndash;717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713&ndash;717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete Latin squares in polynomial time. This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete Latin squares in polynomial time. This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

第一个被证明是 np 完全的自然问题是布尔可满足性问题，也被称为 SAT。如上所述，这就是 Cook-Levin 定理; 它关于可满足性是 NP 完全的证明包含了关于图灵机的技术细节，因为它们与 NP 的定义有关。然而，在这个问题被证明为 np- 完全之后，通过约简证明提供了一种更简单的方法来证明许多其他问题也是 np- 完全的，包括前面讨论过的游戏 Sudoku。在这种情况下，证明了数独在多项式时间内的解也可以用来在多项式时间内完成拉丁方。这反过来又为三部图分割成三角形的问题提供了一个解决方案，三角形可以用来为 SAT 的特殊情形即3-SAT 找到解，从而为一般的布尔可满足性提供了一个解。因此，数独的多项式时间解通过一系列的机械变换，导致可满足性的多项式时间解，而这个多项式时间解又可用于在多项式时间内解决任何其他 np 问题。使用这样的转换，一大类看似不相关的问题都可以归结为彼此，并且在某种意义上是“同一个问题”。

第一个被证明是NP完全的问题是布林满足性问题，也被称为SAT。这也就是库克-里文定理，即，只要SAT问题可以通过确定性图灵机在多项式时间内解决，那么所有NP问题都可以在多项式时间内解决。不过，在这个问题被证明为NP完全之后，又有很多其他问题也被简单的归约证明为NP完全的，如前面讨论过的数独。具体来说，证明数独在多项式时间内的解也可以拓展用在拉丁方阵问题上。再进一步，三分图分割问题的解决为SAT的特殊情形3-SAT问题找到了一个解。因此，通过数独的多项式时间解的一系列变换，得出了SAT的一个多项式时间解，而这个多项式时间解又可用于在多项式时间内解决任何其他NP问题。所以说，一大类看似不相关的问题都可以转换后归化为彼此，在某种意义上就是“同一个问题”。

==Harder problems==

==Harder problems==

Although it is unknown whether P = NP, problems outside of P are known. Just as the class P is defined in terms of polynomial running time, the class EXPTIME is the set of all decision problems that have exponential running time. In other words, any problem in EXPTIME is solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. A decision problem is EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. A number of problems are known to be EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for chess positions on an N × N board and similar problems for other board games.

Although it is unknown whether P = NP, problems outside of P are known. Just as the class P is defined in terms of polynomial running time, the class EXPTIME is the set of all decision problems that have exponential running time. In other words, any problem in EXPTIME is solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. A decision problem is EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. A number of problems are known to be EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for chess positions on an N × N board and similar problems for other board games.

虽然 p = NP 是否存在尚不清楚，但 p 以外的问题是已知的。正如类 p 是根据多项式运行时间定义的一样，类 EXPTIME 是所有具有指数运行时间的决策问题的集合。换句话说，EXPTIME 中的任何问题都可以通过确定性图灵机在 o (2p (n))时间中解决，其中 p (n)是 n 的多项式函数。如果一个决策问题是在 EXPTIME 的，那么它就是 EXPTIME- 完全的，而且 EXPTIME 中的每个问题都有一个多项式时间多次一次约简。已知有许多问题是 EXPTIME-complete 的。因为可以证明 p ≠ EXPTIME，所以这些问题都在 p 之外，所以需要比多项式时间更多的时间。事实上，由美国时间谱系理论协会，他们不能解决显着少于2010年 EXPTIME。例子包括为 n × n 棋盘上的国际象棋位置找到完美的策略，以及为其他棋盘游戏找到类似的问题。

虽然P=NP是否存在尚不清楚，但P类以外的问题是已知的。正如P类是根据多项式时间定义的一样，EXPTIME类判定性问题是所有具有指数时间的问题集合。也就是说，EXPTIME中的任何判定性问题都可以通过确定性图灵机在O(2^p(n))时间内中解决，其中p(n)是n的多项式函数。如果一个判定性问题是在EXPTIME的，那么它就是EXPTIME完全的，而且EXPTIME中的每个问题都有一个多项式时间内的多对一归约。因为我们可以证明P≠EXPTIME，所以所有这些问题都在P类之外，且由时间阶层定理可知，它们的解决不可能远远少于EXPTIME。例如，国际象棋或者其他棋盘游戏中，在已知在N×N棋盘上找到完美的解法就属于EXPTIME类问题。

The problem of deciding the truth of a statement in [[Presburger arithmetic]] requires even more time. [[Michael J. Fischer|Fischer]] and [[Michael O. Rabin|Rabin]] proved in 1974<ref>{{cite journal | first1=Michael J. | last1=Fischer | author-link1=Michael J. Fischer | first2=Michael O. | last2=Rabin | author-link2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41| access-date=15 October 2017 | archive-url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | archive-date=15 September 2006 | url-status=dead }}</ref> that every algorithm that decides the truth of Presburger statements of length ''n'' has a runtime of at least <math>2^{2^{cn}}</math> for some constant ''c''. Hence, the problem is known to need more than exponential run time. Even more difficult are the [[undecidable problem]]s, such as the [[halting problem]]. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

The problem of deciding the truth of a statement in [[Presburger arithmetic]] requires even more time. [[Michael J. Fischer|Fischer]] and [[Michael O. Rabin|Rabin]] proved in 1974<ref>{{cite journal | first1=Michael J. | last1=Fischer | author-link1=Michael J. Fischer | first2=Michael O. | last2=Rabin | author-link2=Michael O. Rabin | date=1974 | title=Super-Exponential Complexity of Presburger Arithmetic | url=http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | journal=Proceedings of the SIAM-AMS Symposium in Applied Mathematics | volume=7 | pages=27–41| access-date=15 October 2017 | archive-url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps | archive-date=15 September 2006 | url-status=dead }}</ref> that every algorithm that decides the truth of Presburger statements of length ''n'' has a runtime of at least <math>2^{2^{cn}}</math> for some constant ''c''. Hence, the problem is known to need more than exponential run time. Even more difficult are the [[undecidable problem]]s, such as the [[halting problem]]. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. Fischer and Rabin proved in 1974 that every algorithm that decides the truth of Presburger statements of length n has a runtime of at least 2^{2^{cn}} for some constant c. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. Fischer and Rabin proved in 1974 that every algorithm that decides the truth of Presburger statements of length n has a runtime of at least 2^{2^{cn}} for some constant c. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

普雷斯伯格算术中确定陈述真实性的问题需要更多的时间。和 Rabin 在1974年证明，每个算法决定真实的 Presburger 语句长度 n 有一个至少2 ^ {2 ^ { cn }的运行时为某个常数 c，因此，该问题是众所周知的需要更多的指数运行时间。更困难的是不可判定的问题，比如停机问题。任何算法都不能完全解决这些问题，因为对于任何特定的算法来说，至少有一个输入的算法不会产生正确的答案; 它要么会产生错误的答案，在没有给出结论性答案的情况下结束，要么永远运行下去而不产生任何答案。

除EXPTIME之外，科学家还发现了所需时间更长的问题。比较标志性的问题是在皮尔斯伯格算术（Presburger arithmetic）中判定任意陈述的正确性的问题。美国计算机学家迈克尔·菲舍尔和以色列数学家迈尔克·罗宾在1974年证明，已知一个皮尔斯伯格语句长度n，判断语句正确性所需的时间至少为2^{2^{cn}，c为常数，该时间比指数时间更长。比这类问题更困难的是不可判定问题，比如停机问题。任何算法都不能完全解决这些问题，因为对于任何特定的算法来说，至少有一个输入的算法不会产生正确的答案；它要么会产生错误的答案，在没有给出结论性答案的情况下结束，要么永远运行下去而不产生任何答案。

It is also possible to consider questions other than decision problems.  One such class, consisting of counting problems, is called [[Sharp-P#P|#P]]: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?"  Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems.<ref>{{cite journal |author=Valiant, Leslie G. |title=The complexity of enumeration and reliability problems |journal=SIAM Journal on Computing |volume=8 |issue=3 |year=1979 |pages=410–421 |doi=10.1137/0208032}}</ref> For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many.  Many of these problems are [[Sharp-P-complete|#P-complete]], and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

It is also possible to consider questions other than decision problems.  One such class, consisting of counting problems, is called [[Sharp-P#P|#P]]: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?"  Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems.<ref>{{cite journal |author=Valiant, Leslie G. |title=The complexity of enumeration and reliability problems |journal=SIAM Journal on Computing |volume=8 |issue=3 |year=1979 |pages=410–421 |doi=10.1137/0208032}}</ref> For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many.  Many of these problems are [[Sharp-P-complete|#P-complete]], and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

It is also possible to consider questions other than decision problems.  One such class, consisting of counting problems, is called #P: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?"  Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems. For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many.  Many of these problems are #P-complete, and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

It is also possible to consider questions other than decision problems.  One such class, consisting of counting problems, is called #P: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?"  Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems. For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many.  Many of these problems are #P-complete, and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

也可以考虑决策问题以外的其他问题。一个这样的类，由计数问题组成，被称为 # p: 而一个 NP 问题问“有解吗?”？”，相应的 # p 问题会问“有多少个解决方案?”很明显，# p 问题必须至少和相应的 NP 问题一样困难，因为如果计数大于零，解的计数会立即告诉你是否至少有一个解存在。令人惊讶的是，一些 # p 问题被认为是困难的对应于简单(例如线性时间)的 p 问题。对于这些问题，很容易判断是否存在解决方案，但很难判断有多少解决方案。这些问题中有许多是 # p 完全的，因此是 # p 中最难的问题之一，因为其中任何一个问题的多项式时间解都允许其他所有 # p 问题的多项式时间解。

判定性问题以外的其他问题也曾被广泛研究，例如#P类，这类问题由计数问题组成。NP类问题讨论的是是否有解，而#P类问题讨论的是有多少个解。很明显，#P类问题至少和相应的NP类问题一样困难，因为如果计数大于零，解的计数会立即告诉你是否至少有一个解存在。但反直觉的是一些#P类问题反而与简单的P类问题范围相交，即很容易判断是否存在解决方案，但很难判断有多少解决方案。这些问题中有许多是#P完全的，也是#P类中最难的问题之一，其中任何一个问题的多项式时间解都将转化为其他所有#P类问题的多项式时间解。

==Problems in NP not known to be in P or NP-complete==

==Problems in NP not known to be in P or NP-complete==

In 1975, Richard E. Ladner showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.

In 1975, Richard E. Ladner showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.

The graph isomorphism problem is the computational problem of determining whether two finite [[Graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{cite journal

The graph isomorphism problem is the computational problem of determining whether two finite [[Graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{cite journal

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai, runs in quasi-polynomial time.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai, runs in quasi-polynomial time.

图同构问题是判定两个有限图是否同构的计算问题。复杂性理论中一个尚未解决的重要问题是图的同构问题是在 p、 np 完全还是 np 中间。答案不得而知，但是人们相信这个问题至少不是 np 完全问题。如果图的同构是 np- 完全的，则多项式时间层次折叠到第二层。由于人们普遍认为 PH 不会塌缩到任何有限的水平，因此人们认为图的同构不是 np 完全的。由于 László Babai 提出的这个问题的最佳算法是在拟多项式时间内运行的。

图同构问题是判定两个有限图是否同构的计算问题。复杂性理论中一个尚未解决的重要问题是图的同构问题是P类、NP完全类还是NP中间类问题。虽然答案还未揭晓，但是人们相信这个问题至少不是NP完全类问题。'''$如果图的同构确实是NP完全类的，则多项式时间层级塌缩到第二层。由于人们普遍认为 PH 不会塌缩到任何有限层，因此人们认为图的同构不是NP完全的。当前最佳的算法由芝加哥大学科学家拉斯洛·巴拜在2015年提出，他的算法是在拟多项式时间解决图的同构问题的。$'''

The [[integer factorization problem]] is the computational problem of determining the [[prime factorization]] of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than ''k''. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the [[RSA (algorithm)|RSA]] algorithm. The integer factorization problem is in NP and in [[co-NP]] (and even in UP and co-UP<ref>[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the [[general number field sieve]], which takes expected time

The [[integer factorization problem]] is the computational problem of determining the [[prime factorization]] of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than ''k''. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the [[RSA (algorithm)|RSA]] algorithm. The integer factorization problem is in NP and in [[co-NP]] (and even in UP and co-UP<ref>[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the [[general number field sieve]], which takes expected time

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UPLance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes expected time

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UPLance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes expected time

整数分解问题是确定一个给定整数的计算问题整数分解。这个问题被称为决策问题，是判断输入的因子是否小于 k 的问题。没有一个有效的整数分解算法是已知的，这个事实形成了一些现代密码系统的基础，比如 RSA 算法。整数分解问题是 NP 完全问题和联合 NP 完全问题(甚至在 UP 和联合上行两周期中也是如此)。计算复杂性博客: 本周的复杂性类: 因数分解。二零零二年九月十三日)。如果问题是 NP 完全的，多项式时间层次将崩溃到它的第一个层次(即，NP = co-NP)。整数分解最著名的算法是普通数域筛选法算法，它需要预期的时间

整数分解问题的核心在于求一个已知整数的质因数分解。它可以被认为是一个决策问题，其核心是判断输入的因子是否小于k。至今我们还未发现一个有效的整数分解算法，这也因此促成了现代密码系统的基础，比如RSA算法。整数分解问题是NP类问题和co-NP类问题，如果它也是NP完全的，多项式时间层次将崩溃到它的第一个层次(即，NP = co-NP)。整数分解最著名的算法是普通数域筛选法算法，它需要预期时间是

:<math>O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )</math>

:<math>O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )</math>

to factor an n-bit integer. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time, although this does not indicate where the problem lies with respect to non-quantum complexity classes.

to factor an n-bit integer. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time, although this does not indicate where the problem lies with respect to non-quantum complexity classes.

==Does P mean "easy"?==

==Does P mean "easy"?==