更改

A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.

A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.

如果一个问题的解决需要大量的资源，无论使用什么算法，那么这个问题本身就被认为是困难的。该理论通过引入数学的'''<font color="#ff8000"> 计算模型Models of computation</font>'''来研究这些问题，并量化它们的'''<font color="#ff8000"> 计算复杂性</font>'''，即解决这些问题所需的资源量，如时间和存储量，将这种直觉形式化。其他复杂性的度量也被使用，例如通信量(用于'''<font color="#ff8000"> 通信复杂性</font>''') ，电路中的逻辑门数(用于'''<font color="#ff8000"> 电路复杂性</font>''')和处理器数(用于'''<font color="#ff8000"> 并行计算</font>''')。'''<font color="#ff8000"> 计算复杂性理论</font>'''的一个作用是确定计算机能做什么和不能做什么的实际限制。'''<font color="#ff8000"> P/NP问题</font>'''，是七大'''<font color="#ff8000"> 千禧年奖问题Millennium Prize Problems</font>'''之一，致力于计算复杂性领域。

如果一个问题的解决需要大量的资源，无论使用什么算法，那么这个问题本身就被认为是困难的。该理论通过引入数学的'''<font color="#ff8000"> 计算模型Models of computation</font>'''来研究这些问题，并量化它们的'''<font color="#ff8000"> 计算复杂性</font>'''，即解决这些问题所需的资源量，如时间和存储量，将这种直觉形式化。其他复杂性的度量也被使用，例如通信量(用于'''<font color="#ff8000"> 通信复杂性</font>''') ，电路中的逻辑门数(用于'''<font color="#ff8000"> 电路复杂性</font>''')和处理器数(用于'''<font color="#ff8000"> 并行计算</font>''')。'''<font color="#ff8000"> 计算复杂性理论</font>'''的一个作用是确定计算机能做什么和不能做什么的实际限制。'''<font color="#ff8000"> P/NP问题</font>'''致力于计算复杂性领域，是七大'''<font color="#ff8000"> 千禧年奖问题Millennium Prize Problems</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>'''。算法分析和计算复杂性理论分析的一个关键区别在于前者致力于分析一个特定算法解决问题所需的资源量，而后者则提出了一个关于所有可能用于解决同一问题的算法的更普遍的问题。更准确地说，计算复杂性理论试图对那些能够或不能够用适当限制的资源来解决的问题进行分类。反过来，对可用资源施加限制是区分计算复杂性和可计算性理论的关键: 后者的理论提出，原则上，什么样的问题可以通过算法来解决。

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

Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.

Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.

文献中提出了许多不同于标准的'''<font color="#ff8000">多带图灵机Multi-tape Turing machines </font>'''的机器模型，例如'''<font color="#ff8000"> 随机存取机Random access machine</font>'''。也许令人惊讶的是，这些模型中的每一个都可以转换成另一个模型，而不需要提供任何额外的计算能力。这些替代模型的时间和内存消耗可能会有所不同。所有这些模型的共同点是，这些机器都是以确定的方式运行的。

文献中提出了许多不同于标准的多带'''<font color="#ff8000">图灵机 </font>'''的机器模型，例如'''<font color="#ff8000"> 随机存取机Random access machine</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)).

为了精确定义在给定的时间和空间内解决问题的意义，我们使用了确定性图灵机这样的计算模型。确定性图灵机 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)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在确定性图灵机上，在时间 f (n)内可解决的问题的集合由 '''<font color="#ff8000"> DTIME(f (n))</font>'''表示。

Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.

Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.

'''<font color="#ff8000"> 平均案例复杂度Average-case complexity</font>''': 这是解决问题的平均复杂度。这种复杂性仅仅定义在输入的概率分布上。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小 n 的所有输入的均匀分布来定义平均案例复杂度。

'''<font color="#ff8000"> 平均案例复杂度Average-case complexity</font>''': 这是解决问题的平均复杂度。这种复杂性仅仅定义在输入的概率分布上。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小为 n 的所有输入的均匀分布来定义平均案例复杂度。

#[[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

#[[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.

The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.

*计算模型：最常见的计算模型是'''<font color="#ff8000"> 确定性图灵机</font>'''，但许多复杂度类是基于'''<font color="#ff8000"> 非确定性图灵机</font>'''，[[布尔电路]]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.

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

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

For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME(n) is contained in DTIME(n²), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.

For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME(n) is contained in DTIME(n²), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.

对于以这种方式定义的复杂类，我们希望证明放宽对计算时间的要求确实定义了更多的问题。特别是，虽然 DTIME (n)包含在 DTIME (n < sup > 2 </sup >)中，但是知道包含是否严格还是很有意思的。对于时间和空间要求，分别用时间和空间层次定理给出了这些问题的答案。它们之所以被称为层次定理，是因为它们通过约束各自的资源，在定义的类上诱导出一个适当的层次结构。因此，存在成对的复杂类，这样一个类可以被正确地包含在另一个类中。我们已经推导出了这种适当的集合包含，我们可以继续进行定量的陈述，说明需要多少额外的时间或空间才能增加可以解决的问题的数量。

对于以这种方式定义的复杂类，我们希望证明放宽对计算时间的要求确实定义了更多的问题。特别是，虽然 DTIME (n)包含在 DTIME (n < sup > 2 </sup >)中，但是知道是否严格包含还是很有意思的。对于时间和空间要求，分别用时间和空间'''<font color="#ff8000">层次定理 </font>'''给出了这些问题的答案。它们之所以被称为'''<font color="#ff8000">层次定理 </font>'''，是因为它们通过约束各自的资源，在定义的类上生成一个适当的层次结构。因此，存在成对的复杂类，一个类可以被正确地包含在另一个类中。通过已经推导出了这种适当的包含集合，我们可以继续进行定量的陈述，说明需要多少额外的时间或空间才能增加可以解决的问题的数量。

The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.

The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.

===Reduction简化===

===Reduction简化===

Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.

Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.

许多复杂性类是使用化简的概念来定义的。化简是将一个问题转化为另一个问题。它抓住了一个非正式的概念，即一个问题最多和另一个问题一样困难。例如，如果一个问题 x 可以用 y 的算法来解决，那么 x 并不比 y 困难，我们说 x 简化为 y。根据简化方法，简化有多种类型，如 Cook 简化、 Karp 简化和 Levin 简化，以及简化复杂度的界限，如多项式时间简化或对数空间简化。

许多复杂性类是使用化简的概念来定义的。化简是将一个问题转化为另一个问题。它抓住了一个非正式的概念，即一个问题最多和另一个问题一样困难。例如，如果一个问题 x 可以用 y 的算法来解决，那么 x 并不比 y 困难，我们说 x 可简化为 y。根据简化方法，简化有多种类型，如 Cook 简化、 Karp 简化和 Levin 简化，以及简化复杂度的界限，如多项式时间简化或对数空间简化。

This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.

This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.

这就产生了一个对于复杂类来说很难解决的问题的概念。如果C中的每一个问题都可以归结为X，那么对于一类问题C来说，问题X是困难的。因此，在C中没有问题比X更难，因为X的算法允许我们在C中解决任何问题。硬问题的概念取决于所用的约化类型。对于大于P的复杂度类，通常使用'''<font color="#ff8000"> 多项式时间图灵归约</font>'''。特别是对NP的难问题集就是'''<font color="#ff8000"> NP难问题</font>'''集。

这就产生了一个对于复杂类来说很难解决的问题的概念。如果C中的每一个问题都可以归结为X，那么对于一类问题C来说，问题X是困难的。因此，在C中没有问题比X更难，因为X的算法允许我们在C中解决任何问题。硬问题的概念取决于所用的简化类型。对于大于P的复杂度类，通常使用'''<font color="#ff8000"> 多项式时间图灵归约</font>'''。特别是NP的难问题集就是'''<font color="#ff8000"> NP难问题</font>'''集。

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.

P 是否等于 NP 的问题是理论计算机科学中最重要的开放性问题之一，因为其解的广泛意义。如果答案是肯定的，那么许多重要的问题就可以得到更有效的解决方案。这些问题包括运筹学中的各种类型的整数规划问题，物流学中的许多问题，生物学中的蛋白质结构预测，以及找到纯数学定理的正式证明的能力。美国 P/NP问题协会是由美国千禧年大奖难题克雷数学研究所提出的一个建议。为了解决这个问题，有一个100万美元的奖金。

P 是否等于 NP 的问题是理论计算机科学中最重要的开放性问题之一，因为其解的广泛意义。如果答案是肯定的，那么许多重要的问题就可以得到更有效的解决方案。这些问题包括运筹学中的各种类型的整数规划问题，物流学中的许多问题，生物学中的蛋白质结构预测，以及找到纯数学定理的正式证明的能力。美国 P/NP问题协会是由美国千禧年大奖难题克雷数学研究所提出的一个建议。为了解决这个问题，设有一个100万美元的奖金。

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the [[Cobham–Edmonds thesis]]. The complexity class [[NP (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the [[Cobham–Edmonds thesis]]. The complexity class [[NP (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

复杂度类P通常被视为一种数学抽象，用于建模那些允许有效算法的计算任务。这个假设被称为[[Cobham-Edmonds论文]]。另一方面，复杂度类[[NP（complexity）| NP]]包含了许多人们想要有效解决的问题，但是没有有效的算法，例如[[布尔可满足性问题]、[[哈密顿路径问题]]和[[顶点覆盖问题]]。由于确定性图灵机是一种特殊的非确定性图灵机，因此很容易观察到P中的每个问题也是NP类的成员。

复杂度类P通常被视为一种数学抽象，用于建模那些允许有效算法的计算任务。这个假设被称为[[Cobham-Edmonds论文]]。另一方面，复杂度类[[NP（复杂度）| NP]]包含了许多人们想要有效解决的问题，但是没有有效的算法，例如[[布尔可满足性问题]、[[哈密顿路径问题]]和[[顶点覆盖问题]]。由于确定性图灵机是一种特殊的非确定性图灵机，因此很容易观察到P中的每个问题也是NP类的成员。

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|url-status=dead|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archivedate=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref>

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|url-status=dead|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archivedate=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref>

It was shown by Ladner that if '''P''' ≠ '''NP''' then there exist problems in '''NP''' that are neither in '''P''' nor '''NP-complete'''.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in '''P''' or to be '''NP-complete'''.

It was shown by Ladner that if '''P''' ≠ '''NP''' then there exist problems in '''NP''' that are neither in '''P''' nor '''NP-complete'''.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in '''P''' or to be '''NP-complete'''.

Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-complete”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或是“NP-complete”。

Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-完全”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或是“NP-完全”。

The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in '''P''', '''NP-complete''', or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation

The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in '''P''', '''NP-complete''', or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆ PP ⊆ PSPACE, but it is possible that P = PSPACE. If P is not equal to NP, then P is not equal to PSPACE either. Since there are many known complexity classes between P and PSPACE, such as RP, BPP, PP, BQP, MA, PH, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆ PP ⊆ PSPACE, but it is possible that P = PSPACE. If P is not equal to NP, then P is not equal to PSPACE either. Since there are many known complexity classes between P and PSPACE, such as RP, BPP, PP, BQP, MA, PH, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

许多已知的复杂类被怀疑是不平等的，但是这还没有被证明。例如 p something NP something PP something PSPACE，但 p = PSPACE 是可能的。如果 p 不等于 NP，那么 p 也不等于 PSPACE。由于 p 和 PSPACE 之间有许多已知的复杂类，如 RP、 BPP、 PP、 BQP、 MA、 PH 等，所有这些复杂类都可能坍缩成一个类。证明这些等级中的任何一个都是不平等的，将是复杂性理论的一个重大突破。

许多已知的复杂类被怀疑是不平等的，但是这还没有被证明。例如 p something NP something PP something PSPACE，但 P = PSPACE 是可能的。如果 P 不等于 NP，那么 P 也不等于 PSPACE。由于 P 和 PSPACE 之间有许多已知的复杂类，如 RP、 BPP、 PP、 BQP、 MA、 PH 等，所有这些复杂类都可能坍缩成一个类。证明这些等级中的任何一个都是不平等的，这将是复杂性理论的一个重大突破。

  | first1 = Vikraman

  | first1 = Vikraman

Along the same lines, co-NP is the class containing the complement problems (i.e. problems with the yes/no answers reversed) of NP problems. It is believed that NP is not equal to co-NP; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then P is not equal to NP, since P=co-P.  Thus if P=NP we would have co-P=co-NP whence NP=P=co-P=co-NP.  

Along the same lines, co-NP is the class containing the complement problems (i.e. problems with the yes/no answers reversed) of NP problems. It is believed that NP is not equal to co-NP; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then P is not equal to NP, since P=co-P.  Thus if P=NP we would have co-P=co-NP whence NP=P=co-P=co-NP.  

同样地，co-NP 也是包含补语问题的类(例如:。问题的是/否回答颠倒)的 NP 问题。人们普遍认为，NP 并不等同于共 NP，然而，这一观点尚未得到证实。很明显，如果这两个复杂度类不相等，那么 p 就不等于 NP，因为 p = co-P。因此，如果 p = NP，我们将得到 co-P = co-NP，其中 NP = p = co-P = co-NP。

同样地，co-NP 也是包含补语问题的类(例如:。问题的是/否回答颠倒)的 NP 问题。人们普遍认为，NP 并不等同于共 NP，然而，这一观点尚未得到证实。很明显，如果这两个复杂度类不相等，那么 P 就不等于 NP，因为 P = co-P。因此，如果 P = NP，我们将得到 co-P = co-NP，其中 NP = P = co-P = co-NP。

  | first2 = Piyush P.

  | first2 = Piyush P.

Similarly, it is not known if L (the set of all problems that can be solved in logarithmic space) is strictly contained in P or equal to P. Again, there are many complexity classes between the two, such as NL and NC, and it is not known if they are distinct or equal classes.

Similarly, it is not known if L (the set of all problems that can be solved in logarithmic space) is strictly contained in P or equal to P. Again, there are many complexity classes between the two, such as NL and NC, and it is not known if they are distinct or equal classes.

同样，l (所有可以在对数空间中解决的问题的集合)是否严格包含在 p 中或等于 p。同样，在两者之间存在着许多复杂类，如 NL 和 NC，它们是不同的还是相等的类。

同样，并不知道L (所有可以在对数空间中解决的问题的集合)是否严格包含在 P 中或等于 P。同样，在两者之间存在着许多复杂类，如 NL 和 NC，也并不知道它们是不同的还是相等的类。

  | title = Graph isomorphism is in SPP

  | title = Graph isomorphism is in SPP

It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP.

It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP.

人们怀疑 P 和 BPP 是相等的。但是，如果 BPP = NEXP，它目前是开放的。

人们怀疑 P 和 BPP 是相等的。但是，如果 BPP = NEXP，它目前就是开放的。

  | volume = 204

  | volume = 204

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is known as an . Conversely, a problem that can be solved in practice is called a , literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization.

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is known as an . Conversely, a problem that can be solved in practice is called a , literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization.

在理论上可以解决的问题。但是在实践中，任何解决方案都需要太多的资源才能发挥作用。相反，一个在实践中可以解决的问题被称为“一个可以处理的问题” ，字面意思是“一个可以处理的问题”。Infeasible (字面上的意思是“不可能完成”)这个词有时候可以和棘手的问题互换使用，尽管这有可能在21最优化被混淆为一个可行的解决方案。

一个问题在理论上可以解决（例如，给定大量但有限的资源，尤其是时间）。但是在实践中，任何解决方案都需要使用太多的资源才能发挥作用。相反，一个在实践中可以解决的问题字面上被称为“一个可以处理的问题” 。术语Infeasible (字面上的意思是“不可能完成”)这个词有时候可以和棘手的互换使用，尽管这有可能在数学优化时被混淆为一个可行的解决方案。

  | postscript = .| doi-access = free

  | postscript = .| doi-access = free

Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.

Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.

易处理的问题经常与具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 退出时间难题extime-hard。如果 NP 不等于 P，那么 NP 难问题在这个意义上也是棘手的。

易处理的问题经常被认为是具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 '''<font color="#ff8000"> 退出时间难题extime-hard</font>'''。如果 NP 不等于 P，那么 '''<font color="#ff8000"> NP 难问题</font>'''在这个意义上也是棘手的。

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2ⁿ operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001ⁿ operations is practical until n gets relatively large.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2ⁿ operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001ⁿ operations is practical until n gets relatively large.

要了解为什么指数时间算法在实践中通常不可用，请考虑一个在暂停之前执行2ⁿ 操作的程序。对于小 n，比如100，假设计算机每秒执行10¹²  操作，程序将运行4&nbsp;×&nbsp;10¹⁰ 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。然而，在 n 变得相对较大之前，使用1.0001ⁿ操作的指数时间算法是可行的。

要了解为什么指数时间算法在实践中通常不可用，请考虑一个在暂停之前执行2ⁿ 操作的程序。对于小的 n，比如100，假设计算机每秒执行10¹²  操作，程序将运行4&nbsp;×&nbsp;10¹⁰ 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。然而，在 n 变得相对较大之前，使用1.0001ⁿ操作的指数时间算法是可行的。

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance '''P''' ⊆ '''NP''' ⊆ '''[[PP (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance '''P''' ⊆ '''NP''' ⊆ '''[[PP (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n³ or n² algorithms are often impractical on realistic sizes of problems.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n¹⁵, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n³ or n² algorithms are often impractical on realistic sizes of problems.

同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n¹⁵ ，那么认为它有效是不合理的，而且除了小实例之外，它仍然是无用的。事实上，在实践中，即使是 n³ 或 n² 算法对于实际问题的大小也常常是不切实际的。

同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n¹⁵ ，那么认为它有效是不合理的，而且除了小的实例之外，它仍然是无用的。事实上，在实践中，即使是 n³ 或 n² 算法对于实际规模的问题也常常是不切实际的。

Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''.  Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.  

Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''.  Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.  

It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.

It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.

有人怀疑“P”和“BPP”相等。但是，如果'''BPP'''=''NEXP''，它当前是打开的。

有人怀疑“P”和“BPP”相等。但是，如果'''BPP'''=''NEXP''，它当前就是开放的。

Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.

Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>

在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}””。<ref>Hopcroft，J.e.，Motwani，R.和Ullman，J.D.（2007）[[自动机理论导论，语言，而计算]]，Addison-Wesley，Boston/San-Francisco/newyork（第368页）</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。

在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft，J.e.，Motwani，R.和Ullman，J.D.（2007）[[自动机理论导论，语言，而计算]]，Addison-Wesley，Boston/San-Francisco/newyork（第368页）</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。

Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.

Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.

The beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity, and proved the hierarchy theorems. In addition, in 1965 Edmonds suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.

The beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity, and proved the hierarchy theorems. In addition, in 1965 Edmonds suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.

计算复杂性系统研究的开始是由于 Juris Hartmanis 和理查德·斯特恩斯在1965年发表的论文《关于算法的计算复杂性》 ，该论文提出了时间复杂性和空间复杂性的定义，并证明了层次定理。此外，在1965年，Edmonds 建议考虑一个”好的”算法是一个运行时间由输入大小的多项式限定的算法。

计算复杂性系统研究的开始是由于 Juris Hartmanis 和理查德·斯特恩斯在1965年发表的论文《关于算法的计算复杂性》 ，该论文提出了时间复杂性和空间复杂性的定义，并证明了层次定理。此外，在1965年，Edmonds 建议考虑一个”好的”算法是一个运行时间由输入规模的多项式限定的算法。

|first=Justin

|first=Justin

In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when the Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.

In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when the Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.

1967年，Manuel-Blum提出了一组公理（现在称为Blum公理），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的加速定理。这一领域在1971年开始蓬勃发展，当时斯蒂芬·库克和列奥尼德·莱文证明了实际相关问题的存在，这些问题是NP完全的。1972年，Richard Karp以其里程碑式的论文《组合问题中的可约性》（reductability In combinational Problems）将这一想法向前推进了一大步。在这篇论文中，他展示了21个不同的组合和图论问题，每一个都因其计算上的困难而臭名昭著，都是NP完全的。

1967年，Manuel-Blum提出了一组公理（现在称为Blum公理），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的加速定理。这一领域在1971年开始蓬勃发展，当时斯蒂芬·库克和列奥尼德·莱文证明了实际相关问题的存在，这些问题是NP完全的。1972年，Richard Karp以其里程碑式的论文《组合问题中的可约性》（reductability In combinational Problems）将这一想法向前推进了一大步。在这篇论文中，他展示了21个不同的组合和图论问题，每一个都因其计算上的困难而声名狼藉，都是NP完全的。

Tractable problems are frequently identified with problems that have polynomial-time solutions ('''P''', '''PTIME'''); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If NP is not the same as P, then [[NP-hard]] problems are also intractable in this sense.

Tractable problems are frequently identified with problems that have polynomial-time solutions ('''P''', '''PTIME'''); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If NP is not the same as P, then [[NP-hard]] problems are also intractable in this sense.

可处理问题通常与具有多项式时间解的问题（''P''，''PTIME''）；这被称为[[Cobham–Edmonds thesis]]。在这个意义上，已知的棘手问题包括[[EXPTIME]]-困难的问题。如果NP与P不同，那么[[NP-hard]]问题在这个意义上也是难以解决的。

可处理问题通常被认为是具有多项式时间解的问题（''P''，''PTIME''）；这被称为[[科巴姆-埃德蒙兹论]]。在这个意义上，已知的棘手问题包括[[EXPTIME]]-困难的问题。如果NP与P不同，那么[[NP-hard]]问题在这个意义上也是难以解决的。

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].

然而，这种辨识是不精确的：具有大阶数或大超前系数的多项式时间解增长很快，对于实际的规模问题可能是不切实际的；相反，缓慢增长的指数时间解在实际输入上可能是实际的，或者在最坏情况下需要很长时间的解可能需要很短的时间时间在大多数情况下还是一般情况下，因此还是实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，[[Presburger algorithm]]中的决策问题已被证明不在P中，但在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次时间的大范围内解决NP完全[[背包问题]]，并且[[SAT solver]]通常处理NP完全[[布尔可满足性问题]]的大型实例。

然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此一般情况下还是实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，[[预伯格算法]]中的决策问题已被证明不在P中，但在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，已有算法可以在小于二次时间的大范围内解决NP完全[[背包问题]]，并且[[SAT solver]]通常能处理NP完全[[布尔可满足性问题]]的大型实例。

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2^''n'' operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001^''n'' operations is practical until ''n'' gets relatively large.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2^''n'' operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10¹² operations each second, the program would run for about 4&nbsp;×&nbsp;10¹⁰ years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001^''n'' operations is practical until ''n'' gets relatively large.

Continuous complexity theory can also refer to complexity theory of the use of [[analog computation]], which uses continuous [[dynamical system]]s and [[differential equation]]s.<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref> [[Control theory]] can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>

Continuous complexity theory can also refer to complexity theory of the use of [[analog computation]], which uses continuous [[dynamical system]]s and [[differential equation]]s.<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref> [[Control theory]] can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>

连续复杂性理论也可以参考复杂性理论中使用的[[模拟计算]]，它使用连续的[[动力系统]]和[[微分方程]]s。[[控制理论]]可以看作是一种计算形式，微分方程用于连续时间和混合离散连续时间系统的建模。

连续复杂性理论也可以参考复杂性理论中使用的[[模拟计算]]，它使用连续的[[动力系统]]和[[微分方程]]s。<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref>[[控制理论]]可以看作是一种计算形式，微分方程用于连续时间和混合离散连续时间系统的建模。<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>

==History历史==

==History历史==

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case{{cn|reason=passive, no source|date=August 2019}}, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>

In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case{{cn|reason=passive, no source|date=August 2019}}, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>

20世纪80年代，人们对NP完全问题的平均困难度和近似解做了大量的工作。当时，计算复杂性理论处于鼎盛时期，人们普遍认为，如果一个问题最终证明是NP完全的，那么在实际情况下处理该问题的可能性很小。然而，越来越清楚的是，{cn | reason=passive，no source | date=2019年8月}的情况并不总是如此，一些作者声称，对于实践中出现的典型问题，一般渐近结果往往不重要。

20世纪80年代，人们对NP完全问题的平均困难度和近似解做了大量的工作。当时，计算复杂性理论处于鼎盛时期，人们普遍认为，如果一个问题最终证明是NP完全的，那么在实际情况下处理该问题的可能性很小。然而，越来越清楚的是情况并不总是如此{{cn|reason=passive, no source|date=August 2019}}，一些作者声称，对于实践中出现的典型问题，一般渐近结果往往不重要。<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>

==Editor's recommendation编辑推荐==

==Editor's recommendation编辑推荐==