更改

===Non-deterministic computation===

===Non-deterministic computation===

In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).

In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).

In a non-deterministic model of computation, such as non-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e.g. Shor's factorization of yet only small integers (: 21 = 3 × 7).

In a non-deterministic model of computation, such as non-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e.g. Shor's factorization of yet only small integers (: 21 = 3 × 7).

在非确定性的计算模型中，例如不确定的图灵机，在计算的某些步骤中可能会有一些选择。在复杂性理论中，一个人同时考虑所有可能的选择，而非确定性的时间复杂性是所需的时间，当最好的选择总是做出。换句话说，我们认为计算是在所需的多个(相同的)处理器上同时进行的，而不确定的计算时间是第一个处理器完成计算所花费的时间。这种并行性在一定程度上可以通过运行特定量子算法的叠加纠缠态来实现量子计算。Shor 的小整数因子分解(: 21 = 3 × 7)。

在'''<font color="#ff8000">非确定性计算模型 non-deterministic model of computation</font>'''中，例如'''<font color="#ff8000">不确定的图灵机 non-deterministic Turing machine</font>'''，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，同时考虑所有可能的选择，当做出最佳选择时，非确定性时间复杂度即为所需的时间。换句话说，我们认为计算是在所需的多个(相同的)处理器上同时进行的，而不确定计算时间是第一个处理器完成计算所花费的时间。这种并行性在一定程度上可以通过运行特定'''<font color="#ff8000">量子算法 quantum algorithm</font>'''的叠加'''<font color="#ff8000">纠缠态 entangled state</font>'''来实现'''<font color="#ff8000">量子计算 quantum computing</font>'''。例如小整数上的'''<font color="#ff8000">肖尔因式分解 Shor's factorization</font>'''。

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.

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及 p = NP 问题，即以“多项式时间”和“非确定性多项式时间”为最小上界所形成的复杂性类的一致性问题。在确定性计算机上模拟 np 算法通常需要“ EXPTIME”。如果一个问题可以在多项式时间内在非确定性机器上求解，则该问题属于复杂类 NP。如果一个问题是 NP 完全问题，粗略地说，它是 NP 问题，并不比任何其他 NP 问题简单。许多组合问题，例如背包问题、旅行推销员问题和布尔可满足性问题问题都是 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===