# 计算复杂性理论

{{简介{计算问题固有难度研究}} 模板:Use mdy dates

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.[1]

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.

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.

Problem instances问题实例 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.

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 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 km. For this reason, complexity theory addresses computational problems and not particular problem instances.

Representing problem instances问题表示实例 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.

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.

Decision problems as formal languages作为形式语言的决策问题 文件:Decision Problem.svg A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input. thumb | A决策问题只有两个可能的输出，任何输入上的“是”或“否”（或交替为1或0）。

A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any 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. 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.

Function problems函数问题 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, b, c) such that the relation a × b = 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, b, c) such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

Measuring the size of an instance测量实例的大小 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?

If the input size is n, the time taken can be expressed as a function of n. Since the time taken on different inputs of the same size can be different, the worst-case time complexity T(n) is defined to be the maximum time taken over all inputs of size n. If T(n) is a polynomial in n, then the algorithm is said to be a polynomial time algorithm. Cobham's thesis argues that a problem can be solved with a feasible amount of resources if it admits a polynomial time algorithm.

If the input size is n, the time taken can be expressed as a function of n. Since the time taken on different inputs of the same size can be different, the worst-case time complexity T(n) is defined to be the maximum time taken over all inputs of size n. If T(n) is a polynomial in n, then the algorithm is said to be a polynomial time algorithm. Cobham's thesis argues that a problem can be solved with a feasible amount of resources if it admits a polynomial time algorithm.

Machine models and complexity measures机器模型与复杂度度量 Turing machine图灵机 Main article: Turing machine 文件:Turing machine 2b.svg An illustration of a Turing machine 拇指|右|图灵机器图解

An illustration of a Turing machine

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.

'图灵机 Turing machine是通用计算机的数学模型。它是一种理论上的设备，可以操纵带条上包含的符号。图灵机并不是作为一种实用的计算技术来使用的，而是作为一种计算机的通用模型，适用于从先进的超级计算机到有铅笔和纸的数学家。研究者们相信如果可以通过算法来解决某个问题，那么就存在解决该问题的图灵机。事实上，这正是邱奇-图灵论题 the Church–Turing thesis的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如 RAM机、Conway的生命游戏、元胞自动机或任何编程语言都可以在图灵机上进行计算。由于图灵机易于进行数学分析，并且被认为与任何其他计算模型一样强大，因此是复杂性理论中最常用的模型。

Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.

Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.

A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.

A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.

Other machine models其他机型 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.[2] 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.

However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems.

However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems.

Complexity measures复杂度度量 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)).

Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.

Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.

The complexity of an algorithm is often expressed using big O notation.

The complexity of an algorithm is often expressed using big O notation.

Best, worst and average case complexity最优、最差和平均案例的复杂度 文件:Sorting quicksort anim.gif Visualization of the quicksort algorithm that has average case performance O(nlogn). thumb |可视化快速排序算法，它具有平均情况性能O(nlogn). Visualization of the quicksort algorithm that has average case performance O(nlogn).

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:

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.

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.

Worst-case complexity: This is the complexity of solving the problem for the worst input of size n. Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.

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.

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(n2). 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(n2). 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.

Upper and lower bounds on the complexity of problems问题复杂性的上下界 To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).

To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).

Upper and lower bounds are usually stated using the big O notation, which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2).

Upper and lower bounds are usually stated using the big O notation, which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2).

Complexity classes复杂度类 Main article: Complexity class

Defining complexity classes定义复杂度类 A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:

A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:

The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems, promise problems, etc. 计算问题的类型：最常用的问题是决策问题。然而，复杂度类可以根据函数问题、计数问题、优化问题、承诺问题等来定义。 The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, Boolean circuits, quantum Turing machines, monotone circuits, 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. 有界的资源（或资源组）及其上下界：这两个属性通常一起表述，如 “多项式时间”、“对数空间”、“常数深度”等。

Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:

Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:

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)).)

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" 模板:Harv. 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.

Important complexity classes重要的复杂度类 文件:Complexity subsets pspace.svg A representation of the relation among complexity classes thumb |右|表示复杂度类之间的关系

A representation of the relation among complexity classes

Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:

Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:

{ | class = “ wikitable” Complexity class Complexity class 复杂度类 Model of computation Model of computation 计算模式 Resource constraint Resource constraint 资源约束 Deterministic time Deterministic time 确定性时间 DTIME(f(n)) DTIME(f(n)) DTIME (f (n)) Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Time O(f(n)) Time O(f(n)) 时间 o (f (n))

P P p Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Time O(poly(n)) Time O(poly(n)) 时间 o (poly (n)) EXPTIME EXPTIME EXPTIME Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Time O(2poly(n)) Time O(2poly(n)) Time o (2 < sup > poly (n) ) Non-deterministic time Non-deterministic time 不确定时间 NTIME(f(n)) NTIME(f(n)) NTIME (f (n)) Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Time O(f(n)) Time O(f(n)) 时间 o (f (n))

NP NP NP Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Time O(poly(n)) Time O(poly(n)) 时间 o (poly (n)) NEXPTIME NEXPTIME NEXPTIME Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Time O(2poly(n)) Time O(2poly(n)) Time o (2 < sup > poly (n) ) { | class = “ wikitable” Complexity class Complexity class 复杂度类

Model of computation Model of computation 计算模式

Resource constraint Resource constraint 资源约束 Deterministic space Deterministic space 确定性空间 DSPACE(f(n)) DSPACE(f(n)) DSPACE (f (n)) Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Space O(f(n)) Space O(f(n)) 空间 o (f (n)) L L l Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Space O(log n) Space O(log n) 空格 o (log n) PSPACE PSPACE PSPACE Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Space O(poly(n)) Space O(poly(n)) 空间 o (poly (n)) EXPSPACE EXPSPACE EXPSPACE Deterministic Turing machine Deterministic Turing machine 确定型图灵机 Space O(2poly(n)) Space O(2poly(n)) 空间 o (2 < sup > poly (n) ) Non-deterministic space Non-deterministic space 非确定性空间 NSPACE(f(n)) NSPACE(f(n)) NSPACE (f (n)) Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Space O(f(n)) Space O(f(n)) 空间 o (f (n)) NL NL NL Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Space O(log n) Space O(log n) 空格 o (log n) NPSPACE NPSPACE NPSPACE Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Space O(poly(n)) Space O(poly(n)) 空间 o (poly (n)) NEXPSPACE NEXPSPACE NEXPSPACE Non-deterministic Turing machine Non-deterministic Turing machine 非确定型图灵机

Space O(2poly(n)) Space O(2poly(n)) 空间 o (2 < sup > poly (n) )

|}

|}

The logarithmic-space classes (necessarily) do not take into account the space needed to represent the problem.

The logarithmic-space classes (necessarily) do not take into account the space needed to represent the problem.

It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem.

It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem.

Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.

Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.

Hierarchy theorems层次定理 Main articles: time hierarchy theorem和space hierarchy theorem 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(n2), 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(n2), 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.

More precisely, the time hierarchy theorem states that

More precisely, the time hierarchy theorem states that

Undefined control sequence \sdot. Undefined control sequence \sdot.

The space hierarchy theorem states that

The space hierarchy theorem states that

Undefined control sequence \sdot. Undefined control sequence \sdot.

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归约 Main article: Reduction (complexity) 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.

The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.

The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.

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.

If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π2, to another problem, Π1, would indicate that there is no known polynomial-time solution for Π1. This is because a polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.[3]

If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π2, to another problem, Π1, would indicate that there is no known polynomial-time solution for Π1. This is because a polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.]]

Important open problems重要的开放性问题 文件:Complexity classes.svg Diagram of complexity classes provided that P ≠ NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.[4] 假设P≠NP的复杂性类的拇指图。在这种情况下，P和NP完全问题的NP问题的存在性是由拉德纳Ladner证明的。

P versus NP problemP vs 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, 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.

Main article: P versus NP 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 vs NP问题是克雷数学研究所提出的千年大奖问题之一。解决该问题的奖金为100000美元。 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, 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包含了许多人们想要有效解决的问题，但是尚无有效的算法，例如布尔可满足性问题 the Boolean satisfiability problem 哈密顿路径问题 the Hamiltonian path problem 顶点覆盖问题 the vertex cover problem 。由于确定型图灵机是一种特殊的非确定型图灵机，因此很容易观察到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.[3] 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,[5] and the ability to find formal proofs of pure mathematics theorems.[6] 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.[7]

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai and Eugene Luks has run time O(2nlogn√) for graphs with n vertices, although some recent work by Babai offers some potentially new perspectives on this.

Ladner指出，如果P≠NP，则NP中存在既不是P也不是NP完全的问题。如果图同构 graph isomorphism 是NP完全的，则多项式时间层次会塌缩到第二级。由于人们普遍认为多项式族不会塌缩到任何有限水平，因此图同构不是NP完全的。由于László Babai和Eugene Luks的缘故，针对此问题的最佳算法对具有n个顶点的图的运行时间为O（2nlogn√），尽管Babai最近的一些工作对此提供了一些潜在的新观点。

Problems in NP not known to be in P or NP-complete NP中不知是P或NP完全问题的问题 The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time O(e(649√3)(logn)√3(loglogn)2√3) to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.[4] 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.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are 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.[8] If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level.[9] Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai and Eugene Luks has run time O(2nlogn√) for graphs with n vertices, although some recent work by Babai offers some potentially new perspectives on this.[10]

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.

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP[11]). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time O(e(649√3)(logn)√3(loglogn)2√3)[12] to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

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.

Separations between other complexity classes其他复杂度类之间的分离 To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2n operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 1012 operations each second, the program would run for about 4 × 1010 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.0001n operations is practical until n gets relatively large.

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.

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

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[15] 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. 同 “即，问题的答案与‘NP’的问题是相反的。据信[16] “NP”不等于“co-NP”，但它还没有被证明。很明显，如果这两个复杂度类不相等，那么“P”就不等于“NP”，因为“P”=“co-P”。因此，如果P=NP，我们将有co-P'=co-NP，其中NP=P=co-P=co-NP。

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.

Continuous complexity theory can refer to complexity theory of problems that involve continuous functions that are approximated by discretizations, as studied in numerical analysis. One approach to complexity theory of numerical analysis is information based complexity.

It is suspected that P and BPP are equal. However, it is currently open if 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.

Intractability难解性 脚本错误：没有“Labelled list hatnote”这个模块。

An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

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.[17] Conversely, a problem that can be solved in practice is called a 模板:Visible anchor, literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable,[18] though this risks confusion with a feasible solution in mathematical optimization.引用错误：没有找到与</ref>对应的<ref>标签相反，一个可以在实践中解决的问题称为“模板:Visible anchor”，字面意思是“可以处理的问题”。术语不可行（字面意思是“不能做”）有时与“棘手”互换使用，尽管这有可能与数学优化中的可行解混淆。[19] though this risks confusion with a feasible solution in mathematical optimization.[20]

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年开始蓬勃发展，当时斯蒂芬·库克 Stephen Cook和列奥尼德·莱文 Leonid Levin证明了实际相关问题的存在，这些问题是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.

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.

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

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 2n operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 1012 operations each second, the program would run for about 4 × 1010 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.0001n operations is practical until n gets relatively large.

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

Continuous complexity theory连续复杂性理论 Continuous complexity theory can refer to complexity theory of problems that involve continuous functions that are approximated by discretizations, as studied in numerical analysis. One approach to complexity theory of numerical analysis[21] is information based complexity. 连续复杂性理论可以指问题的复杂性理论，这些问题涉及通过离散化近似的连续函数，如数值分析中所研究的那样。数值分析复杂性理论的一种方法是基于信息的复杂性。

Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations.[22] 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.[23]

History历史 An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

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.[26] 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.[27]

Earlier papers studying problems solvable by Turing machines with specific bounded resources include[26] John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's study of rudimentary sets (1961), as well as Hisao Yamada's paper[28] on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure.[29] As he remembers:

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

line-height: 1.5em;
/* @noflip */
text-align: left;
/* @noflip */
margin-top: 0;

}

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.[30]

1967年，Manuel Blum提出了一组公理s（现在称为Blum axioms），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的加速定理。这个领域在1971年开始蓬勃发展，当时Stephen Cook和Leonid Levin[[Cook–Levin定理|证明了NP complete实际相关问题的存在。1972年，Richard Karp以其里程碑式的论文《组合问题中的可还原性》（Reductibility In Combinational Problems）将这一想法向前推进了一大步，在这篇论文中，他展示了21个不同的组合和图论问题，每一个都因其计算难处理而声名狼藉，是NP完全的。[31]

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, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.[32]

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

1 = Arora | first1 = Sanjeev | authorlink1 = Sanjeev Arora

Context of computational complexity 计算复杂性的上下文 | last2=Barak | first2=Boaz

2 = Barak | first2 = Boaz

Descriptive complexity theory | title=Computational Complexity: A Modern Approach

| title = 计算复杂性: 一种现代方法

Game complexity | url = http://www.cs.princeton.edu/theory/complexity/

Leaf language | publisher=Cambridge University Press

Limits of computation | year=2009

2009年

List of complexity classes | isbn=978-0-521-42426-4

| isbn = 978-0-521-42426-4

List of computability and complexity topics | zbl=1193.68112

1193.68112

List of important publications in theoretical computer science }}

}}

List of unsolved problems in computer science Parameterized complexity | last1=Downey

1 = Downey

Proof complexity | first1=Rod

1 = Rod

Quantum complexity theory | last2=Fellows

2 = Fellows

Structural complexity theory | first2=Michael

2 = Michael

2 = Michael Fellows

Computational complexity of mathematical operations | title=Parameterized complexity

| publisher=Springer-Verlag

| publisher = Springer-Verlag

Works on complexity复杂性的研究 | location=Berlin, New York

| 地点: 柏林，纽约

Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, doi:10.1142/11270, ISBN 978-981-12-0006-9 | year=1999

1999年

| isbn=9780387948836

9780387948836

References参考文献 | series=Monographs in Computer Science

Citations 引用 }}

}}

"P vs NP Problem | Clay Mathematics Institute". www.claymath.org (in English).
See 脚本错误：没有“Footnotes”这个模块。
See 脚本错误：没有“Footnotes”这个模块。
Ladner, Richard E. (1975), "On the structure of polynomial time reducibility", Journal of the ACM, 22 (1): 151–171, doi:10.1145/321864.321877.
Berger, Bonnie A.; Leighton, T (1998), "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete", Journal of Computational Biology, 5 (1): 27–40, CiteSeerX 10.1.1.139.5547, doi:10.1089/cmb.1998.5.27, PMID 9541869.
Cook, Stephen (April 2000), The P versus NP Problem (PDF), Clay Mathematics Institute, archived from the original (PDF) on December 12, 2010, retrieved October 18, 2006.
Jaffe, Arthur M. (2006), "The Millennium Grand Challenge in Mathematics" (PDF), Notices of the AMS, 53 (6), retrieved October 18, 2006.
{{Citation 图同构问题是确定两个有限图是否为同构的计算问题。复杂度理论中一个重要的未解决的问题是图的同构问题是在“P”、“NP-完全”还是NP-中间。答案不得而知，但人们相信这个问题至少不是NP完全的。 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 等，所有这些复杂类都可能坍缩成一个类。证明这些等级中的任何一个都是不平等的，这将是复杂性理论的一个重大突破。 | first1 = Vikraman | last1 = Arvind 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。 | first2 = Piyush P. | last2 = Kurur 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，也并不知道它们是不同的还是相等的类。 | title = Graph isomorphism is in SPP | journal = Information and Computation It is suspected that P and BPP are equal. However, it is currently open if BPP = NEXP. 人们怀疑 P 和 BPP 是相等的。但是，如果 BPP = NEXP，它目前就是开放的。 | volume = 204 | issue = 5

Intractability难处理性 = = 棘手 = = = < ! -- 本节链接于 minimax，棘手，棘手 -- >

| year = 2006 | pages = 835–852 | doi = 10.1016/j.ic.2006.02.002 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.

| postscript = .| doi-access = free }}

Schöning, Uwe (1987). Graph isomorphism is in the low hierarchy. Lecture Notes in Computer Science. 1987. pp. 114–124. doi:10.1007/bfb0039599. ISBN 978-3-540-17219-2.
Babai, László (2016). "Graph Isomorphism in Quasipolynomial Time". arXiv:1512.03547 [cs.DS].
Fortnow, Lance (September 13, 2002). "Computational Complexity Blog: Factoring". weblog.fortnow.com.
Wolfram MathWorld: Number Field Sieve
{cite web | first=Lance | last=Fortnow | authorlink=Lance Fortnow | title=计算复杂性博客：Factoring | date=2002-09-13 | url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html%7C网站=博客.fortnow.com}}
Wolfram MathWorld:[1]
Boaz Barak's course on Computational Complexity Lecture 2
Boaz Barak's course on Computational Complexity Lecture 2
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)
Meurant, Gerard (2014). Algorithms and Complexity. p. p. 4. ISBN 978-0-08093391-7.
Meurant, Gerard (2014). Algorithms and Complexity. p. p. 4. ISBN 978-0-08093391-7.
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. 在真正致力于研究算法问题的复杂性的实际研究开始之前，许多研究人员都打下了大量的基础。其中最有影响力的是阿兰 · 图灵在1936年对图灵机的定义，这被证明是一个非常健壮和灵活的计算机简化。 Zobel Earlier papers studying problems solvable by Turing machines with specific bounded resources include on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure. As he remembers: 早期研究图灵机在特定资源限制下可解决问题的论文包括实时计算(1962)。更早些时候，Boris Trakhtenbrot (1956) ，苏联在这一领域的先驱，研究了另一个具体的复杂性度量。正如他所记得的:, Justin (2015). Writing for Computer Science 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 建议考虑一个”好的”算法是一个运行时间由输入规模的多项式限定的算法。. p. 132. ISBN 978-1-44716639-9.
Smale, Steve (1997). "Complexity Theory and Numerical Analysis". Acta Numerica. Cambridge Univ Press. 6: 523–551. Bibcode:1997AcNum...6..523S. doi:10.1017/s0962492900002774. 模板:Citeseerx.
Babai, László; Campagnolo, Manuel (2009). "A Survey on Continuous Time Computations". arXiv:0907.3117 [cs.CC].
Tomlin, Claire J.; Mitchell, Ian; Bayen, Alexandre M.; Oishi, Meeko (July 2003). "Computational Techniques for the Verification of Hybrid Systems". Proceedings of the IEEE. 91 (7): 986–1001. doi:10.1109/jproc.2003.814621. 模板:Citeseerx.
Babai, László; Campagnolo, Manuel (2009). "A Survey on Continuous Time Computations". arXiv:0907.3117 [cs.CC].
Tomlin, Claire J.; Mitchell, Ian; Bayen, Alexandre M.; Oishi, Meeko (July 2003). "Computational Techniques for the Verification of Hybrid Systems". Proceedings of the IEEE. 91 (7): 986–1001. doi:10.1109/jproc.2003.814621. 模板:Citeseerx.

Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture
Yamada, H. (1962). "Real-Time Computation and Recursive Functions Not Real-Time Computable". IEEE Transactions on Electronic Computers. EC-11 (6): 753–760. doi:10.1109/TEC.1962.5219459.
Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski 早期研究图灵机器在特定有界资源下可解问题的论文包括Yamada, H. "实时计算和递归函数不可实时计算". IEEE电子计算机事务. doi:10.1109/TEC.1962.5219459. Unknown parameter |卷= ignored (help); Unknown parameter |页= ignored (help); Unknown parameter |问题= ignored (help); Unknown parameter |年= ignored (help) Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (in Russian)
Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller; J. W. Thatcher (eds.), Complexity of Computer Computations, New York: Plenum, pp. 85–103
Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller; J. W. Thatcher (eds.), Complexity of Computer Computations, New York: Plenum, pp. 85–103
Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc.. p. 1143. ISBN 978-1-57955-008-0.
Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc.. p. 1143. ISBN 978-1-57955-008-0.

| last=Du

| last = Du

Textbooks教材 | first=Ding-Zhu

| 第一 = 鼎柱

Arora, Sanjeev; Barak, Boaz (2000 2000年), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-471-34506-0 line feed character in |year= at position 5 (help); More than one of |author2= and |last2= specified (help); Check date values in: |year= (help)

}}

| year=2009

| isbn=978-0-521-42426-4

| zbl=1193.68112

| last=Goldreich

| last = Goldreich

}}

| first=Oded

Downey, Rod; Fellows, Michael (2008 2008年), [http://www.wisdom.weizmann.ac.il/~oded/cc-book.html

Http://www.wisdom.weizmann.ac.il/~oded/cc-book.html 计算复杂性: 一个概念性的视角] Check |url= value (help), Cambridge University Press

}}

| title=Parameterized complexity

| editor1-last=van Leeuwen

| editor1-last=van Leeuwen

| publisher=Springer-Verlag

| editor1-first=Jan

1-first = Jan

| location=Berlin, New York

| editor1-link = Jan van Leeuwen

| editor1-link = Jan van Leeuwen

| year=1999

| title=Handbook of theoretical computer science (vol. A): algorithms and complexity

| title = 理论计算机科学手册。A)算法和复杂性

| isbn=9780387948836

| publisher=MIT Press

| publisher = MIT Press

| series=Monographs in Computer Science

| isbn=978-0-444-88071-0

| isbn = 978-0-444-88071-0

}}

| year=1990

1990年

Empty citation (help) }}

| last=Du

| first=Ding-Zhu

| author2=Ko, Ker-I

| first = Christos 第一季，克里斯托

| title=Theory of Computational Complexity

| publisher=John Wiley & Sons

| title = Computational Complexity | title = 计算复杂性

| year=2000

| edition = 1st 1st

| isbn=978-0-471-34506-0

| year = 1994 1994年

}}

| publisher = Addison Wesley 艾迪生 · 韦斯利

Empty citation (help) }}

| last=Goldreich

| first=Oded

|last=Sipser

|first=Michael

| title = Computational Complexity: A Conceptual Perspective

|title=Introduction to the Theory of Computation

| title = 美国计算理论学会简介

| publisher = Cambridge University Press

|edition=2nd

2nd

| year = 2008

|year=2006

2006年

}}

|publisher=Thomson Course Technology

| publisher = Thomson Course Technology

van Leeuwen, Jan (ed.), USA, ISBN 978-0-534-95097-2 Missing or empty |title= (help) }}

| title=Handbook of theoretical computer science (vol. A): algorithms and complexity

| publisher=MIT Press

| isbn=978-0-444-88071-0

| year=1990

}}

Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7 {{Citation |last=Sipser

|first=Michael