更改

[[Computational complexity]] theory focuses on classifying [[computational problem]]s according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an [[algorithm]].

[[Computational complexity]] theory focuses on classifying [[computational problem]]s according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an [[algorithm]].

[[计算复杂性]]理论关注于根据资源使用情况对[[计算问题]]进行分类，并将这些类相互关联。计算问题是由计算机解决的任务。计算问题可以通过机械地应用数学步骤来解决，例如[[算法]]。

[[计算复杂性]]理论关注于根据资源使用情况对[[计算问题]]进行分类，并将这些类相互关联。计算问题是可由计算机解决的任务。计算问题可以通过机械地应用数学步骤来解决，例如[[算法]]。

Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

'''<font color="#ff8000"> 计算复杂性理论Computational complexity theory</font>'''的重点是根据计算问题的资源使用情况对其进行分类，并将这些类相互关联。计算问题是一个能由计算机解决的任务。计算问题是可以通过机械应用的数学步骤，例如算法来解决的。

'''<font color="#ff8000"> 计算复杂性理论Computational complexity theory</font>'''的重点是根据计算问题的资源使用情况对其进行分类，并将这些类相互关联。计算问题是能由计算机解决的任务。计算问题是可以通过机械应用的数学步骤来解决的，例如算法。

Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.

Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.

理论计算机科学中密切相关的领域是'''<font color="#ff8000"> 算法分析Analysis of algorithms</font>'''和'''<font color="#ff8000"> 可计算性理论Computability theory</font>'''。算法分析和计算复杂性理论分析的一个关键区别在于前者致力于分析一个特定算法解决问题所需的资源量，而后者则提出了一个关于所有可能用于解决同一问题的算法的更普遍的问题。更准确地说，计算复杂性理论试图对那些能够或不能够用适当限制的资源来解决的问题进行分类。反过来，对可用资源施加限制是区分计算复杂性和可计算性理论的关键: 后者的理论提出，原则上，什么样的问题可以通过算法来解决。

理论计算机科学中与其密切相关的领域是'''<font color="#ff8000"> 算法分析Analysis of algorithms</font>'''和'''<font color="#ff8000"> 可计算性理论Computability theory</font>'''。<font color="#ff8000"> 算法分析</font>和<font color="#ff8000"> 计算复杂性理论</font>的一个关键区别在于前者致力于分析一个特定算法解决问题所需的资源量，而后者则提出了一个更普遍的问题，关于所有可能用于解决同一问题的算法的。更准确地说，<font color="#ff8000"> 计算复杂性理论</font>试图对那些能够或不能够用适当限制的资源来解决的问题进行分类。反过来，对可用资源施加限制是区分计算复杂性和可计算性理论的关键: 后者的理论提出，原则上，什么样的问题可以通过算法来解决。

A [[decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input.]]

A [[decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input.]]

一个[[决策问题只有两个可能的输出，对任何输入是或否(或者交替1或0)]]

一个[[决策问题对任何输入只有两个可能的输出，是或否(或者交替1或0)]]

[[Decision problem]]s are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either ''yes'' or ''no'', or alternately either 1 or 0. A decision problem can be viewed as a [[formal language]], where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an [[algorithm]], whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer ''yes'', the algorithm is said to accept the input string, otherwise it is said to reject the input.

[[Decision problem]]s are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either ''yes'' or ''no'', or alternately either 1 or 0. A decision problem can be viewed as a [[formal language]], where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an [[algorithm]], whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer ''yes'', the algorithm is said to accept the input string, otherwise it is said to reject the input.

An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.

An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.

'''<font color="#ff8000"> 决策问题</font>'''的一个例子如下。输入是一个任意的'''<font color="#ff8000"> 图</font>'''。问题是判断给定的图是否连通。与这个决策问题相关的形式语言是所有连通图的集合ーー为了获得这种语言的精确定义，必须决定图是如何编码成二进制字符串的。

'''<font color="#ff8000"> 决策问题</font>'''的一个例子如下。输入是一个任意的'''<font color="#ff8000"> 图</font>'''。问题是判断给定的图是否连通。与这个决策问题相关的形式语言是所有连通图的集合ーー为了获得这种语言的精确定义，必须决定<font color="#ff8000"> 图</font>是如何编码成二进制字符串的。

===Function problems函数问题===

===Function problems函数问题===

To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?

To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?

A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.

A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.

'''<font color="#ff8000"> 图灵机Turing machine</font>'''是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。图灵机器并不是一种实用的计算技术，而是一种计算机的通用模型，（适用于）从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个图灵机器来解决这个问题。事实上，这正是'''<font color="#ff8000"> 丘奇-图灵论题Church–Turing thesis</font>'''的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如'''<font color="#ff8000"> RAM机器、Conway的生命游戏、元胞自动机</font>'''或任何编程语言都可以在图灵机器上进行计算。由于图灵机易于数学分析，并且被认为与任何其他计算模型一样强大，因此是复杂性理论中最常用的模型。

'''<font color="#ff8000"> 图灵机Turing machine</font>'''是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。<font color="#ff8000"> 图灵机</font>并不是一种实用的计算技术，而是一种计算机的通用模型，（适用于）从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个<font color="#ff8000"> 图灵机</font>来解决这个问题。事实上，这正是'''<font color="#ff8000"> 丘奇-图灵论题Church–Turing thesis</font>'''的表述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如'''<font color="#ff8000"> RAM机器、Conway的生命游戏、元胞自动机</font>'''或任何编程语言都可以在<font color="#ff8000"> 图灵机</font>上进行计算。由于<font color="#ff8000"> 图灵机</font>易于数学分析，并且被认为与任何其他计算模型一样强大，因此是<font color="#ff8000"> 复杂性理论</font>中最常用的模型。

For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).

For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).

为了精确定义在给定的时间和空间内解决问题的意义，我们使用了'''<font color="#ff8000">确定性图灵机 </font>'''这样的计算模型。确定性图灵机 M 在输入 x 上所需的时间是该机在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 M 对每个长度 n 的输入所需的时间最多为 f (n) ，则称 M 在时间 f (n)内工作。如果存在一个在时间 f (n)内运行的图灵机，决策问题 A 就可以在时间 f (n)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在确定性图灵机上，在时间 f (n)内可解决的问题的集合由 '''<font color="#ff8000"> DTIME(f (n))</font>'''表示。

为了精确定义在给定的时间和空间内解决问题的意义，我们使用了'''<font color="#ff8000">确定性图灵机 </font>'''这样的计算模型。确定性图灵机 M 在输入 x 上所需的时间是该机在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 M 对每个长度 n 的输入所需的时间最多为 f (n) ，则称 M 在时间 f (n)内运行。如果存在一个在时间 f (n)内运行的图灵机，决策问题 A 就可以在时间 f (n)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在<font color="#ff8000">确定性图灵机 </font>上，在时间 f (n)内可解决的问题的集合由 '''<font color="#ff8000"> DTIME(f (n))</font>'''表示。

The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n may be faster to solve than others, we define the following complexities:

The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n may be faster to solve than others, we define the following complexities:

'''<font color="#ff8000"> 最佳、最差和平均情况复杂度</font>'''是指三种不同的方法来度量相同大小的不同输入的时间复杂度(或任何其他复杂度度量)。由于一些 n 大小的输入可能比其他的更快解决，我们定义了以下复杂性:

'''<font color="#ff8000"> 最佳、最差和平均情况复杂度</font>'''是指用三种不同的方法来度量相同大小的不同输入的时间复杂度(或任何其他复杂度度量)。由于一些 n 大小的输入可能比其他的更快解决，我们定义了以下复杂性:

#Best-case complexity: This is the complexity of solving the problem for the best input of size ''n''.

#Best-case complexity: This is the complexity of solving the problem for the best input of size ''n''.

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n²). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n²). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.

例如，考虑确定性排序算法'''<font color="#ff8000"> 快速排序Quicksort</font>'''。这解决了对作为输入的整数列表进行排序的问题。最坏的情况是轴总是列表中的最大值或最小值（因此列表永远不会被拆分）。在这种情况下，算法需要时间O(n²)。如果我们假设输入列表的所有可能的排列都是相同的，那么排序所花费的平均时间是O(n log n)。最好的情况发生在每次旋转将列表分成两半时，也需要O(n log n)时间。

例如，考虑确定性排序算法'''<font color="#ff8000"> 快速排序Quicksort</font>'''。它解决了对作为输入的整数列表进行排序的问题。最坏的情况是轴总是列表中的最大值或最小值（因此列表永远不会被拆分）。在这种情况下，算法需要时间O(n²)。如果我们假设输入列表的所有可能的排列都是相同的，那么排序所花费的平均时间是O(n log n)。最好的情况发生在每次旋转将列表分成两半时，也需要O(n log n)时间。

===Upper and lower bounds on the complexity of problems问题复杂性的上下界===

===Upper and lower bounds on the complexity of problems问题复杂性的上下界===

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

时间 f (n)内<font color="#ff8000">确定性图灵机 </font>可解决的<font color="#ff8000">决策问题 </font>集。(这个复杂性类称为 '''<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 是一组<font color="#ff8000">决策问题 </font>，可以由<font color="#ff8000">确定性图灵机 </font>在<font color="#ff8000">多项式时间 </font>内解决。相应的一组函数问题是 FP。

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

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

<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.

<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.