更改

* The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on [[function problem]]s, [[counting problem (complexity)|counting problem]]s, [[optimization problem]]s, [[promise problem]]s, etc.

* The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on [[function problem]]s, [[counting problem (complexity)|counting problem]]s, [[optimization problem]]s, [[promise problem]]s, etc.

*计算问题的类型：最常用的问题是决策问题。然而，复杂度类可以基于[[函数问题]]s、[[计数问题（复杂性）|计数问题]]s、[[优化问题]]s、[[承诺问题]]等定义。

*计算问题的类型：最常用的问题是'''<font color="#ff8000"> 决策问题</font>'''。然而，复杂度类可以基于[[函数问题]]s、[[计数问题（复杂性）|计数问题]]s、[[优化问题]]s、[[承诺问题]]等定义。

* The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, [[Boolean circuit]]s, [[quantum Turing machine]]s, [[monotone circuit]]s, etc.

* The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, [[Boolean circuit]]s, [[quantum Turing machine]]s, [[monotone circuit]]s, etc.

*计算模型：最常见的计算模型是确定性图灵机，但许多复杂度类是基于非确定性图灵机，[[布尔电路]]s，[[量子图灵机]]s，[[单调电路]]s等。

*计算模型：最常见的计算模型是'''<font color="#ff8000"> 确定性图灵机</font>'''，但许多复杂度类是基于'''<font color="#ff8000"> 非确定性图灵机</font>'''，[[布尔电路]]s，[[量子图灵机]]s，[[单调电路]]s等。

* The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.

* The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.

*有界的资源和有界资源：这两个属性通常一起表述，如“多项式时间”、“对数空间”、“常数深度”等。

*有界的资源（或资源组）和有界资源：这两个属性通常一起表述，如“多项式时间”、“对数空间”、“常数深度”等。

The set of decision problems solvable by a deterministic Turing machine within time f(n). (This complexity class is known as DTIME(f(n)).)

The set of decision problems solvable by a deterministic Turing machine within time f(n). (This complexity class is known as DTIME(f(n)).)

时间 f (n)内确定性图灵机可解决的决策问题集。(这个复杂性类称为 DTIME (f (n))。)

时间 f (n)内确定性图灵机可解决的决策问题集。(这个复杂性类称为 '''<font color="#ff8000"> DTIME (f (n))</font>'''。)

But bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.

But bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.

但是通过一些具体的函数 f (n)来限定上面的计算时间通常会产生依赖于所选择的机器模型的复杂类。例如，语言{ xx | x 是任意二进制字符串}可以在多带图灵机上用线性时间求解，但在单带图灵机模型中需要二次时间。如果我们允许运行时间的多项式变化，Cobham-Edmonds 理论指出，”任何两个合理的和一般的计算模型的时间复杂性是多项式相关的”。这就形成了复杂度等级 p 的基础，p 是一组决策问题，可以由确定性图灵机在多项式时间内解决。相应的一组函数问题是 FP。

但是通过一些具体的函数 f (n)来限定上面的计算时间通常会产生依赖于所选择的机器模型的复杂类。例如，语言{ xx | x 是任意二进制字符串}可以在多带图灵机上用线性时间求解，但在单带图灵机模型中需要二次时间。如果我们允许运行时间的多项式变化，Cobham-Edmonds 理论指出，”任何两个合理的和一般的计算模型的时间复杂性是多项式相关的”。这就形成了复杂度等级 P 的基础，P 是一组决策问题，可以由确定性图灵机在多项式时间内解决。相应的一组函数问题是 FP。

 

 

===Important complexity classes重要的复杂性类===

===Important complexity classes重要的复杂性类===