更改

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.

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.

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

如果一个问题的解决需要大量的资源，无论使用什么算法，那么这个问题本身就被认为是困难的。该理论通过引入数学的'''<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>'''。算法分析和计算复杂性理论分析的一个关键区别在于前者致力于分析一个特定算法解决问题所需的资源量，而后者则提出了一个关于所有可能用于解决同一问题的算法的更普遍的问题。更准确地说，计算复杂性理论试图对那些能够或不能够用适当限制的资源来解决的问题进行分类。反过来，对可用资源施加限制是区分计算复杂性和可计算性理论的关键: 后者的理论提出，原则上，什么样的问题可以通过算法解决。

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input.

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input.

一个计算问题可以被看作是一个实例的无限集合和每个实例的解决方案。计算问题的输入字符串被称为问题实例，不应与问题本身混淆。在计算复杂性理论，问题指的是要解决的抽象问题。相比之下，这个问题的实例是一个相当具体的表述，可以作为决策问题的输入。例如，考虑素性测试的问题。实例是一个数字(例如，15) ，如果数字是质数，解决方案是“是” ，否则是“否”(在这种情况下，15不是质数，答案是“否”)。换句话说，实例是问题的特定输入，解决方案是与给定输入对应的输出。

一个'''<font color="#ff8000"> 计算问题</font>'''可以被看作是一个实例的无限集合和每个实例的解决方案。'''<font color="#ff8000"> 计算问题</font>'''的输入字符串被称为问题实例，不应与问题本身混淆。在计算复杂性理论，问题指的是要解决的抽象问题。相比之下，这个问题的实例是一个相当具体的表述，可以作为决策问题的输入。例如，考虑素性测试的问题。实例是一个数字(例如，15) ，如果数字是质数，解决方案是“是” ，否则是“否”(在这种情况下，15不是质数，答案是“否”)。换句话说，实例是问题的特定输入，解决方案是与给定输入对应的输出。

To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10&nbsp;km. For this reason, complexity theory addresses computational problems and not particular problem instances.

To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10&nbsp;km. For this reason, complexity theory addresses computational problems and not particular problem instances.

为了进一步突出问题和实例之间的区别，考虑以下关于旅行推销员问题的决策版本: 是否有一条最多2000公里的路线穿过德国所有15个最大的城市？这个特殊问题的定量答案对于解决这个问题的其他实例没有什么用处，例如要求在米兰的所有地点进行往返旅行，这些地点的总长度最多不超过10公里。基于这个原因，复杂性理论解决的是计算问题而不是特定的问题实例。

为了进一步突出问题和实例之间的区别，考虑以下关于旅行推销员问题的决策版本: 是否有一条最多2000公里的路线穿过德国所有15个最大的城市？这个特殊问题的定量答案对于解决这个问题的其他实例没有什么用处，例如要求在米兰的所有地点进行往返旅行，这些地点的总长度最多不超过10公里。基于这个原因，'''<font color="#ff8000"> 复杂性理论</font>'''解决的是'''<font color="#ff8000"> 计算问题</font>'''而不是特定的问题实例。

When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary.

When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary.

在考虑计算问题时，问题实例是字母表上的字符串。通常，字母表被认为是二进制字母表(即集合{0,1}) ，因此字符串是位字符串。在现实世界的计算机中，除了位字符串以外的数学对象必须进行适当的编码。例如，整数可以用二进制表示法表示，图可以通过它们的邻接矩阵直接进行编码，或者用二进制编码它们的邻接列表。

在考虑'''<font color="#ff8000"> 计算问题</font>'''时，一个问题实例是字母表上的字符串。通常，字母表被认为是二进制字母表(即集合{0,1}) ，因此字符串是位字符串。在现实世界的计算机中，除了位字符串以外的数学对象必须进行适当的编码。例如，整数可以用二进制表示法表示，图可以通过它们的'''<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.

Decision problems 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 problems 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 (discrete mathematics)|graph]]. The problem consists in deciding whether the given graph is [[connectivity (graph theory)|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 (discrete mathematics)|graph]]. The problem consists in deciding whether the given graph is [[connectivity (graph theory)|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.

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.

A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem.

A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem.

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a,&nbsp;b,&nbsp;c) such that the relation a&nbsp;×&nbsp;b&nbsp;=&nbsp;c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a,&nbsp;b,&nbsp;c) such that the relation a&nbsp;×&nbsp;b&nbsp;=&nbsp;c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

人们很容易认为函数问题的概念比决策问题的概念丰富得多。然而，事实并非如此，因为函数问题可以被改写为决策问题。例如，两个整数的乘法可以表示为三元组（a，b，c），这样关系a&nbsp;×&nbsp;b&nbsp;=&nbsp;c成立。决定一个给定的三元组是否是这个集合的一员相当于解决两个数相乘的问题。

人们很容易认为'''<font color="#ff8000"> 函数问题</font>'''的概念比'''<font color="#ff8000"> 决策问题</font>'''的概念丰富得多。然而，事实并非如此，因为函数问题可以被改写为决策问题。例如，两个整数的乘法可以表示为三元组（a,&nbsp;b,&nbsp;c），这样关系a&nbsp;×&nbsp;b&nbsp;=&nbsp;c成立。决定一个给定的三元组是否是这个集合的一员相当于解决两个数相乘的问题。