更改

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

虽然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 name=":16">{{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.

<nowiki>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.</nowiki>

<nowiki>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.</nowiki>

除EXPTIME之外，科学家还发现了所需时间更长的问题。比较标志性的问题是在皮尔斯伯格算术（Presburger arithmetic）中判定任意陈述的正确性的问题。美国计算机学家迈克尔·菲舍尔和以色列数学家迈尔克·罗宾在1974年证明，已知一个皮尔斯伯格语句长度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 name=":17">{{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类问题是用多项式运行时间定义的，EXPTIME类问题是所有具有指数运行时间决策问题的集合。换句话说，EXPTIME中的任何问题都可以利用确定性图灵机在O(2^''p(n)'')时间内解决，其中''p(n)''是n的多项式函数。如果某个决策问题在EXPTIME类中，并且EXPTIME中的每个问题都可以通过多项式时间一次性归约（[[wikipedia:Many-one_reduction|many-one reduction]]）得到该问题，那么这个问题是EXPTIME完全的。许多问题都是EXPTIME完全的。<u>因此可以说明P ≠ EXPTIME，这些问题不属于P类，并且所需时间远超多项式时间。</u>【原文的because前后，我并没理解这个逻辑关系。在[[wikipedia:P_versus_NP_problem#Harder_problems|该节]] 第一段Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. 】实际上，根据时间层次定理，它们不能在显著少于指数时间的情况下求解。例如，在''N''×''N''的国际象棋棋盘上找到一个下棋的完美策略，<ref name="Fraenkel1981" />或是其他类似的棋类游戏。<ref name=":15" />

虽然不知道P = NP是否成立，但P类之外的问题是已知的。正如P类问题是用多项式运行时间定义的，EXPTIME类问题是所有具有指数运行时间决策问题的集合。换句话说，EXPTIME中的任何问题都可以利用确定性图灵机在O(2^''p(n)'')时间内解决，其中''p(n)''是n的多项式函数。如果某个决策问题在EXPTIME类中，并且EXPTIME中的每个问题都可以通过多项式时间一次性归约（[[wikipedia:Many-one_reduction|many-one reduction]]）得到该问题，那么这个问题是EXPTIME完全的。许多问题都是EXPTIME完全的。<u>因此可以说明P ≠ EXPTIME，这些问题不属于P类，并且所需时间远超多项式时间。</u>【原文的because前后，我并没理解这个逻辑关系。在[[wikipedia:P_versus_NP_problem#Harder_problems|该节]] 第一段Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. 】实际上，根据时间层次定理，它们不能在显著少于指数时间的情况下求解。例如，在''N''×''N''的国际象棋棋盘上找到一个下棋的完美策略，<ref name="Fraenkel1981" />或是其他类似的棋类游戏。<ref name=":15" />

在普雷斯伯格算术中判断语句是否为真需要更多的时间。费舍尔（Fischer）和拉宾（Rabin）在1974年证明，任何算法判定一条长度为n的普雷斯伯格语句为真的运行时间至少是<math>2^{2^{cn}}</math>。因此，已知该问题需要超过指数级运行时间。更困难的是不可判定问题，例如停机问题。任何算法都无法完全解决这些问题，因为对于任何特定的算法，至少有一个输入，该算法无法给出正确的答案；它要么给出错误的答案，要么在没有给出正确的答案就结束了，要么永远运行，根本没有给出任何答案。

在普雷斯伯格算术中判断语句是否为真需要更多的时间。费舍尔（Fischer）和拉宾（Rabin）在1974年证明，<ref name=":16" />任何算法判定一条长度为n的普雷斯伯格语句为真的运行时间至少是<math>2^{2^{cn}}</math>，c是某常数。因此，该问题运行时间远超指数级。更困难的是不可判定问题，例如停机问题。任何算法都无法完全解决这些问题，因为对于任何特定的算法，至少有一个输入，该算法无法给出正确答案；它要么给出错误答案，要么在没有给出正确答案前就结束了，或是永远运行，根本没有给出任何答案。

除了判定问题之外也有值得考虑的问题。其中一类由计数问题组成，称为#P：与NP问题会问“有什么解决方案吗？”不同，相应的#P问题问“有多少种解决方案？”显然，一个#P问题至少和相应的NP问题一样难，因为如果解的个数大于零，这个计数值会立即告诉我们是否至少存在一个解。令人惊讶的是，一些被认为是困难的#P问题，其对应的P问题（例如线性时间）是简单的。对于这些问题，很容易判断是否存在解决方案，但很难判断有多少种解决方案。这些问题中有许多是#P-完全的，因此是#P中最难的问题之一，因为对其中任何一个问题的多项式时间解都将使得所有其他#P问题有多项式时间解。

除了判定问题之外也有值得考虑的问题。其中一类是计数问题，称为#P：与NP问题会问“有什么解决方法吗？”不同，对应的#P问题会问“有多少种解决方法？”显然，一个#P问题至少和对应的NP问题一样难，因为如果问题的解的个数大于零，这个计数值就告诉我们是否至少存在一个解。令人惊讶的是，一些被认为是困难的#P问题，其对应的P问题（例如线性时间）是简单的。<ref name=":17" />对于这些问题，很容易判断是否存在解决方法，但很难判断有多少种解决方法。这些问题中有许多是#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==