更改

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''<font color="#ff8000">P = NP?</font>''' 问题。如果一个问题可以在确定性图灵机上以'''<font color="#ff8000">多项式时间 polynomial time</font>'''求解，则该问题属于 '''<font color="#ff8000">P 类问题</font>'''。如果一个问题可以在非确定性机器上以'''<font color="#ff8000">多项式时间 polynomial time</font>'''求解，则该问题属于 '''<font color="#ff8000">NP 类问题</font>'''。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''<font color="#ff8000">P = NP?</font>''' 问题。如果一个问题可以在确定性图灵机上以'''<font color="#ff8000">多项式时间 polynomial time</font>'''求解，则该问题属于 '''<font color="#ff8000">P 类问题</font>'''。如果一个问题可以在非确定性机器上以'''<font color="#ff8000">多项式时间 polynomial time</font>'''求解，则该问题属于 '''<font color="#ff8000">NP 类问题</font>'''。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题

如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为'''<font color="#ff8000"> NP完全问题  NP-complete</font>'''。许多'''<font color="#ff8000">组合 combinatorial</font>'''问题，例如'''<font color="#ff8000">背包问题 Knapsack problem</font>'''、'''<font color="#ff8000">旅行推销员问题 travelling salesman problem</font>'''和'''<font color="#ff8000">布尔可满足性问题 Boolean satisfiability problem</font>'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP，既。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即。

如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为'''<font color="#ff8000"> NP完全问题  NP-complete</font>'''。许多'''<font color="#ff8000">组合 combinatorial</font>'''问题，例如'''<font color="#ff8000">背包问题 Knapsack problem</font>'''、'''<font color="#ff8000">旅行推销员问题 travelling salesman problem</font>'''和'''<font color="#ff8000">布尔可满足性问题 Boolean satisfiability problem</font>'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP，既。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。

===Parallel and distributed computation===

===Parallel and distributed computation===