更改

[[Image:Complexity classes.svg|thumb|Diagram of complexity classes provided that P&nbsp;≠&nbsp;NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] |volume=22|year=1975|pages=151–171|doi=10.1145/321864.321877|issue=1|postscript=.}}</ref>]]

[[Image:Complexity classes.svg|thumb|Diagram of complexity classes provided that P&nbsp;≠&nbsp;NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] |volume=22|year=1975|pages=151–171|doi=10.1145/321864.321877|issue=1|postscript=.}}</ref>]]

[[图片：Complexity classes.svg|假设P≠NP的复杂性类的拇指图。在这种情况下，P和NP完全外的NP问题的存在性是由Ladner证明的。

[[图片：Complexity classes.svg|假设P≠NP的复杂性类的拇指图。在这种情况下，P和NP完全问题的NP问题的存在性是由拉德纳Ladner证明的。]]

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

复杂性类 p 通常被看作是一个数学抽象，为那些需要高效算法的计算任务建模。这一假设被称为“科布姆-埃德蒙兹论”。另一方面，复杂性类 NP 包含了许多人们想要高效率解决的问题，但是对于这些问题却没有一个有效的算法，比如布尔可满足性问题、哈密顿路径问题和覆盖。由于确定性图灵机是一种特殊的非确定性图灵机，很容易观察到 p 中的每个问题都是 NP 类的成员。

复杂度类P通常被视为一种数学抽象，用于建模那些允许有效算法的计算任务。这个假设被称为'''<font color="#ff8000"> 科巴姆-埃德蒙兹论Cobham–Edmonds thesis</font>'''。另一方面，复杂度类NP包含了许多人们想要有效解决的问题，但是没有有效的算法，例如'''<font color="#ff8000"> 布尔可满足性问题、哈密顿路径问题和顶点覆盖问题</font>'''。由于确定性图灵机是一种特殊的非确定性图灵机，因此很容易观察到P中的每个问题也是NP类的成员。

 

{{Main|P versus NP problem}}

{{Main|P versus NP problem}}

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the [[Cobham–Edmonds thesis]]. The complexity class [[NP (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the [[Cobham–Edmonds thesis]]. The complexity class [[NP (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

 

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|url-status=dead|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archivedate=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref>

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|url-status=dead|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archivedate=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref>

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor 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 and Eugene Luks has run time <math>O(2^{\sqrt{n \log n}})</math> for graphs with n vertices, although some recent work by Babai offers some potentially new perspectives on this.

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor 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 and Eugene Luks has run time <math>O(2^{\sqrt{n \log n}})</math> for graphs with n vertices, although some recent work by Babai offers some potentially new perspectives on this.

Ladner 指出，如果 p 不等于 NP，那么在 NP 中就存在既不是 p 也不是 NP 完全的问题。如果图的同构是 np- 完全的，则多项式时间层次折叠到第二层。由于人们普遍认为 PH 不会塌缩到任何有限的水平，因此人们认为图的同构不是 np 完全的。这个问题最好的算法，由于 László Babai 和 Eugene Luks 已经运行时 < math > o (2 ^ { sqrt { n log n }) </math > 对于 n 个顶点的图，尽管 Babai 最近的一些工作提供了一些潜在的新观点。

Ladner指出，如果P≠NP，则NP中存在既不是P也不是NP完全的问题。如果图同构是NP完全的，则多项式时间层次会塌缩到第二级。由于人们普遍认为多项式族不会塌缩到任何有限水平，因此图同构不是NP完全的。尽管Babai最近的一些工作提供了一些潜在的新观点，这个问题的最佳算法，属于Lászlóbai和Eugene Luks，他们已经对于有n个顶点的图运行了时间<math>O(2^{\sqrt{n \log n}})</math>。

===Problems in NP not known to be in P or NP-completeNP中不知道P或NP完全的问题===

===Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题===

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 prime 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-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

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 prime 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-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

整数分解问题是确定一个给定整数的计算问题整数分解。这个问题被称为决策问题，是决定输入是否有一个素因子小于 k 的问题没有一个有效的整数分解算法是已知的，这个事实形成了一些现代密码系统的基础，比如 RSA 算法。整数分解问题是 NP 和 co-NP (甚至是 UP 和 co-UP)的问题。如果问题是 NP 完全的，多项式时间层次将崩溃到它的第一个层次(即，NP 将等于 co-NP)。整数分解最著名的算法是普通数域筛选法算法，它需要时间 < math > o (e ^ { left (sqrt [3]{ frac {64}{9}右) sqrt [3]{(log n)} sqrt [3]{(log log log n) ^ 2}) </math > 计算奇数 n。然而，最著名的量子算法，Shor 的算法，在多项式时间内运行。不幸的是，这个事实并没有说明问题出在哪里，关于非量子复杂性类。

'''<font color="#ff8000"> 整数因式分解问题</font>'''是确定给定整数的素数因式分解的计算问题。作为一个'''<font color="#ff8000"> 决策问题</font>'''，它是判断输入是否有一个小于k的素数因子的问题。目前还没有有效的整数分解算法，这一事实构成了几种现代密码系统的基础，如'''<font color="#ff8000"> RSA算法</font>'''。整数分解问题存在于NP和co-NP中（甚至在UP和co-UP中）。如果问题是'''<font color="#ff8000"> NP完全问题</font>'''，多项式时间层次将崩溃到第一级（即NP等于co-NP）。最著名的整数因式分解算法是一般的数域筛，它需要时间<math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math>来分解一个奇数n。但是，这个问题最著名的量子算法'''<font color="#ff8000"> Shor算法</font>'''是在多项式时间内运行的。不幸的是，这一事实并不能说明非量子复杂性类的问题所在。

 

It was shown by Ladner that if '''P''' ≠ '''NP''' then there exist problems in '''NP''' that are neither in '''P''' nor '''NP-complete'''.<ref name="Ladner75" /> 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'''.

It was shown by Ladner that if '''P''' ≠ '''NP''' then there exist problems in '''NP''' that are neither in '''P''' nor '''NP-complete'''.<ref name="Ladner75" /> 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'''.

Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-complete”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或“NP-complete”。

Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-complete”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或是“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">{{Citation

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">{{Citation

It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP.

It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP.

人们怀疑 p 和 BPP 是相等的。但是，如果 BPP = NEXP，它目前是开放的。

人们怀疑 P 和 BPP 是相等的。但是，如果 BPP = NEXP，它目前是开放的。

  | volume = 204

  | volume = 204

Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.

Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.

易处理的问题经常与具有多项式时间解决方案的问题(p，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 extime-hard。如果 NP 不等于 p，那么 NP 难问题在这个意义上也是棘手的。

易处理的问题经常与具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 退出时间难题extime-hard。如果 NP 不等于 P，那么 NP 难问题在这个意义上也是棘手的。

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2ⁿ operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001ⁿ operations is practical until n gets relatively large.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2ⁿ operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001ⁿ operations is practical until n gets relatively large.

要了解为什么指数时间算法在实践中通常不可用，请考虑一个在暂停之前执行2个 < sup > n </sup > 操作的程序。对于小 n，比如100，假设计算机每秒执行10个 < sup > 12个 </sup > 操作，程序将运行4 × 10 </sup > 10 </sup > 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。然而，在 n 变得相对较大之前，使用1.0001 < sup > n </sup > 操作的指数时间算法是可行的。

要了解为什么指数时间算法在实践中通常不可用，请考虑一个在暂停之前执行2ⁿ 操作的程序。对于小 n，比如100，假设计算机每秒执行10¹² 操作，程序将运行4&nbsp;×&nbsp;10¹⁰ 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。然而，在 n 变得相对较大之前，使用1.0001ⁿ操作的指数时间算法是可行的。

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance '''P''' ⊆ '''NP''' ⊆ '''[[PP (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance '''P''' ⊆ '''NP''' ⊆ '''[[PP (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n³ or n² algorithms are often impractical on realistic sizes of problems.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n³ or n² algorithms are often impractical on realistic sizes of problems.

同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n < sup > 15 </sup > ，那么认为它有效是不合理的，而且除了小实例之外，它仍然是无用的。事实上，在实践中，即使是 n < sup > 3 </sup > 或 n < sup > 2 </sup > 算法对于实际问题的大小也常常是不切实际的。

同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n¹⁵ ，那么认为它有效是不合理的，而且除了小实例之外，它仍然是无用的。事实上，在实践中，即使是 n³ 或 n² 算法对于实际问题的大小也常常是不切实际的。

Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''.  Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.  

Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''.  Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.  

It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.

It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.

有人怀疑“P”和“BPP”是相等的。但是，如果'''BPP'''=''NEXP''，它当前是打开的。

有人怀疑“P”和“BPP”相等。但是，如果'''BPP'''=''NEXP''，它当前是打开的。

Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.

Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.

An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

算法复杂性分析的一个早期例子是 Gabriel lamé 在1844年对辗转相除法的运行时间分析。

算法复杂性分析的一个早期例子是 Gabriel lamé 在1844年对欧几里德算法的运行时间分析。

{{wikt|tractable|feasible|intractability|infeasible}}

{{wikt|tractable|feasible|intractability|infeasible}}

In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when the Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.

In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when the Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.

1967年，Manuel Blum 提出了一组公理(现在称为 Blum 公理) ，在可计算函数集上指定了复杂度量的理想性质，并证明了一个重要的结果，即所谓的加速定理。这个领域在1971年开始蓬勃发展，当时史蒂芬 · 库克和莱昂尼德 · 莱文证明存在实际上相关的 np 完全问题。1972年，理查德 · 卡普在他具有里程碑意义的论文《组合问题中的可约性》中，向我们展示了21个不同的组合和图论问题，每个问题都因其难以计算而臭名昭著，这是 np 完全的。

1967年，Manuel-Blum提出了一组公理（现在称为Blum公理），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的加速定理。这一领域在1971年开始蓬勃发展，当时斯蒂芬·库克和列奥尼德·莱文证明了实际相关问题的存在，这些问题是NP完全的。1972年，Richard Karp以其里程碑式的论文《组合问题中的可约性》（reductability In combinational Problems）将这一想法向前推进了一大步。在这篇论文中，他展示了21个不同的组合和图论问题，每一个都因其计算上的困难而臭名昭著，都是NP完全的。

 

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.

 

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2^''n'' operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001^''n'' operations is practical until ''n'' gets relatively large.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2^''n'' operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001^''n'' operations is practical until ''n'' gets relatively large.

要了解为什么指数时间算法在实际中通常不可用，请考虑一个在停止之前进行2次^“n'操作的程序。对于小的“n”，比如100，假设计算机每秒进行10次^12次操作，程序将运行大约4×10¹⁰年，与[[宇宙年龄]]的数量级相同。即使有一台速度快得多的计算机，该程序也只对非常小的实例有用，从这个意义上说，一个问题的棘手程度在某种程度上与技术进步无关。然而，在“n”变得相对较大之前，需要1.0001^“n”运算的指数时间算法是可行的。

要了解为什么指数时间算法在实际中通常不可用，请考虑一个在停止之前进行2^''n''操作的程序。对于小的“n”，比如100，假设计算机每秒进行10¹² 操作，程序将运行大约4&nbsp;×&nbsp;10¹⁰年，与[[宇宙年龄]]的数量级相同。即使有一台速度快得多的计算机，该程序也只对非常小的实例有用，从这个意义上说，一个问题的棘手程度在某种程度上与技术进步无关。然而，在“n”变得相对较大之前，需要1.0001^''n'' 运算的指数时间算法是可行的。

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ''n''¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ''n''³ or ''n''² algorithms are often impractical on realistic sizes of problems.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ''n''¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ''n''³ or ''n''² algorithms are often impractical on realistic sizes of problems.

类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”¹⁵，那么认为它是有效的是不合理的，而且除了在小实例上，它仍然是无用的。实际上，在实践中，即使是“n”³或“n”²算法对于实际大小的问题往往是不切实际的。

类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”¹⁵，那么认为它是有效的是不合理的，而且除了在小实例上，它仍然是无用的。实际上，在实践中，即使是''n''³ 或 ''n''² 算法对于实际大小的问题往往是不切实际的。

==Continuous complexity theory连续复杂性理论==

==Continuous complexity theory连续复杂性理论==