更改

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 理论。在这个意义上被认为是棘手的问题包括那些 '''<font color="#ff8000"> 退出时间难题extime-hard</font>'''。如果 NP 不等于 P，那么 '''<font color="#ff8000"> NP 难问题</font>'''在这个意义上也是棘手的。

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

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.

然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。

然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。

===Separations between other complexity classes其他复杂性类之间的分离===

===Separations between other complexity classes其他复杂性类之间的分离===