更改

Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the P = NP problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class NP, if it may be solved in polynomial time on a non-deterministic machine. A problem is NP-complete if, roughly speaking, it is in NP and is not easier than any other NP problem. Many combinatorial problems, such as the Knapsack problem, the travelling salesman problem, and the Boolean satisfiability problem are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP.  it is generally conjectured that  with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.

Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the P = NP problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class NP, if it may be solved in polynomial time on a non-deterministic machine. A problem is NP-complete if, roughly speaking, it is in NP and is not easier than any other NP problem. Many combinatorial problems, such as the Knapsack problem, the travelling salesman problem, and the Boolean satisfiability problem are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP.  it is generally conjectured that  with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''<font color="#ff8000">P = NP</font>'''问题，即以“多项式时间”和“非确定性多项式时间”为最小上界所形成的复杂度类的一致性问题。在确定性计算机上模拟 NP算法通常需要“指数时间”。如果一个问题可以在在非确定性机器上'''<font color="#ff8000">多项式时间 polynomial time</font>'''内求解，则该问题属于复杂类 '''<font color="#ff8000">NP</font>'''。如果一个问题是'''<font color="#ff8000"> NP完全问题  NP-complete</font>'''，粗略地说，该问题属于 NP 问题，不比其他任何 NP 问题简单。许多'''<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。一般认为，伴随着实际意义，NP 问题的最坏情况本质上是难以解决的，也就是说，需要的时间比任何合理的时间跨度(几十年!)有趣的输入长度。

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''<font color="#ff8000">P = NP</font>'''问题，即以“多项式时间”和“非确定性多项式时间”为最小上界所形成的复杂度类的一致性问题。在确定性计算机上模拟 NP算法通常需要“指数时间”。如果一个问题可以在在非确定性机器上'''<font color="#ff8000">多项式时间 polynomial time</font>'''内求解，则该问题属于复杂类 '''<font color="#ff8000">NP</font>'''。如果一个问题是'''<font color="#ff8000"> NP完全问题  NP-complete</font>'''，粗略地说，该问题属于 NP 问题，不比其他任何 NP 问题简单。许多'''<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。一般认为，伴随着实际意义，NP 问题的最坏情况本质上是难以解决的，也就是说，比任何合理的时间跨度(几十年!)都要长。

===Parallel and distributed computation===

===Parallel and distributed computation===