561
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共5448，未经人工整理和审校，带来阅读不便，请见谅。+ − + + + 第29行：
第31行： − + − + 第39行：
第41行： − + 第57行：
第59行： − + 第75行：
第77行： − + + + 第87行：
第91行： − 决策问题是计算复杂性理论的中心研究对象之一。决策问题是一种特殊类型的计算问题问题，它的答案要么是是或否，要么是1或0。决策问题可以看作是一种形式语言，其中语言的成员是其输出为 yes 的实例，而非成员是其输出为 no 的实例。其目的是借助算法来决定一个给定的输入字符串是否是所考虑的形式语言的成员。如果决定这个问题的算法返回的答案是肯定的，那么算法就说接受输入字符串，否则就说拒绝输入。+ − − 第99行：
第101行： − + 第105行：
第107行： − 函数问题是一个计算问题问题，其中每个输入都期望有一个单独的输出(一个总函数的输出) ，但输出比决策问题更复杂ーー也就是说，输出不仅仅是“是”或“否”。值得注意的例子包括旅行推销员问题和整数分解问题。+ − 第113行：
第114行： − 函数问题的概念比决策问题的概念要丰富得多。然而，实际情况并非如此，因为函数问题可以被重写为决策问题。例如，两个整数的乘法可以表示为三元组的集合(a，b，c) ，这样关系 a × b = c 就成立。判断一个给定的三元组是否是该集合的一个成员，相当于解决了两个数相乘的问题。+ − + 第123行：
第124行： − 要衡量解决一个计算问题问题的难度，你可能希望看到最好的算法需要多少时间来解决这个问题。但是，通常情况下，运行时间可能取决于实例。特别是，更大的实例将需要更多的时间来解决。因此，解决问题所需的时间(或所需的空间，或任何复杂性度量)是按实例大小的函数计算的。这通常被认为是输入位的大小。复杂性理论的兴趣在于算法如何随着输入大小的增加而扩展。例如，在寻找一个图是否连通的问题中，与寻找一个有 n 个顶点的图相比，寻找一个有2n 个顶点的图需要多少时间来解决一个问题？+ + 第135行：
第137行： − + − + + 第153行：
第156行： − 图灵机是通用计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。图灵机并不是一种实用的计算机技术，而是一种计算机的通用模型ーー从一台高级超级计算机到一个拿着铅笔和纸的数学家。人们相信，如果一个问题可以通过算法来解决，那么就存在一个图灵机来解决这个问题。事实上，这就是丘奇-图灵论点的陈述。此外，众所周知，所有可以在我们今天已知的其他计算模型上计算的东西，例如 RAM 机器、 Conway 的生命游戏、细胞自动机或任何编程语言都可以在图灵机上计算。由于图灵机易于进行数学分析，并且被认为和其他任何计算模型一样强大，因此图灵机是复杂性理论中最常用的模型。+ − 第173行：
第175行： − + 第191行：
第193行： − + 第213行：
第215行： − + − + − + − + 第271行：
第273行： − + 第277行：
第279行： − + 第285行：
第287行： − + − + 第295行：
第297行： − + 第304行：
第306行： − + − + − + 第335行：
第337行： − + + 第935行：
第938行： − + 第983行：
第986行： − + 第1,019行：
第1,022行： − + + − + 第1,051行：
第1,055行： − + 第1,059行：
第1,063行： + + − The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in '''P''', '''NP-complete''', or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation+ 第1,095行：
第1,101行： − + 第1,120行：
第1,126行： + + 第1,127行：
第1,135行： − + 第1,135行：
第1,143行： − + 第1,143行：
第1,151行： + + − 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.+ 第1,154行：
第1,164行： + + 第1,161行：
第1,173行： − + 第1,172行：
第1,184行： + + 第1,208行：
第1,222行： + + 第1,217行：
第1,233行： − + − + + − + − − + + − + − − + − + + + − Earlier papers studying problems solvable by Turing machines with specific bounded resources include<ref name="Fortnow 2003"/> [[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<ref>{{Cite journal | last1 = Yamada | first1 = H. | title = Real-Time Computation and Recursive Functions Not Real-Time Computable | journal = IEEE Transactions on Electronic Computers | volume = EC-11 | issue = 6 | pages = 753–760 | year = 1962 | doi = 10.1109/TEC.1962.5219459}}</ref> on real-time computations (1962). Somewhat earlier, [[Boris Trakhtenbrot]] (1956), a pioneer in the field from the USSR, studied another specific complexity measure.<ref>Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski+ 第1,263行：
第1,281行： − + + − + − 第1,278行：
第1,296行： − + 第1,399行：
第1,417行： − + 第1,413行：
第1,431行： − + 第1,730行：
第1,748行： − +
无编辑摘要
此词条暂由水流心不竞初译，翻译字数共，未经审校，带来阅读不便，请见谅。
{{short description|Study of inherent difficulty of computational problems}}
{{short description|Study of inherent difficulty of computational problems}}
{{简介{计算问题固有难度研究}}
{{Use mdy dates|date=September 2017}}
{{Use mdy dates|date=September 2017}}
[[Computational complexity]] theory focuses on classifying [[computational problem]]s according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an [[algorithm]].
[[Computational complexity]] theory focuses on classifying [[computational problem]]s according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an [[algorithm]].
[[计算复杂性]]理论关注于根据资源使用情况对[[计算问题]]进行分类，并将这些类相互关联。计算问题是由计算机解决的任务。计算问题可以通过机械地应用数学步骤来解决，例如[[算法]]。
Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
==Computational problems==
==Computational problems计算问题==
[[Image:TSP Deutschland 3.png|thumb|upright=1.5|A traveling salesman tour through 14 German cities.]]
[[Image:TSP Deutschland 3.png|thumb|upright=1.5|A traveling salesman tour through 14 German cities.]]
[[图片：TSP Deutschland3.png |拇指|直立=1.5 |旅行推销员在14个德国城市旅行。]]
A traveling salesman tour through 14 German cities.
A traveling salesman tour through 14 German cities.
===Problem instances===
===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.
===Representing problem instances===
===Representing problem instances问题表达实例===
When considering computational problems, a problem instance is a [[string (computer science)|string]] over an [[Alphabet (computer science)|alphabet]]. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are [[bitstring]]s. As in a real-world [[computer]], mathematical objects other than bitstrings must be suitably encoded. For example, [[integer]]s can be represented in [[binary notation]], and [[graph (discrete mathematics)|graph]]s can be encoded directly via their [[adjacency matrix|adjacency matrices]], or by encoding their [[adjacency list]]s in binary.
When considering computational problems, a problem instance is a [[string (computer science)|string]] over an [[Alphabet (computer science)|alphabet]]. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are [[bitstring]]s. As in a real-world [[computer]], mathematical objects other than bitstrings must be suitably encoded. For example, [[integer]]s can be represented in [[binary notation]], and [[graph (discrete mathematics)|graph]]s can be encoded directly via their [[adjacency matrix|adjacency matrices]], or by encoding their [[adjacency list]]s in binary.
===Decision problems as formal languages===
===Decision problems as formal languages作为形式语言的决策问题===
[[Image:Decision Problem.svg|thumb|A [[decision problem]] has only two possible outputs, ''yes'' or ''no'' (or alternately 1 or 0) on any input.]]
[[Image:Decision Problem.svg|thumb|A [[decision problem]] has only two possible outputs, ''yes'' or ''no'' (or alternately 1 or 0) on any input.]]
[[图：Decision Problem.svg|thumb | A[[决策问题]]只有两个可能的输出，任何输入上的“是”或“否”（或交替为1或0）。]]
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.]]
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.
决策问题是计算复杂性理论研究的中心内容之一。决策问题是一种特殊类型的计算问题，其答案要么是“是”，要么是“否”，要么是“1”或“0”。决策问题可以看作是一种形式语言，语言的成员是输出为“是”的实例，而非成员是输出为“否”的实例，其目的是借助算法来确定给定的输入字符串是否是所考虑的形式语言的成员。如果决定这个问题的算法返回的答案是“是”，则表示该算法接受输入字符串，否则表示拒绝输入。
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.
===Function problems===
===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]].
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.
人们很容易认为函数问题的概念比决策问题的概念丰富得多。然而，事实并非如此，因为函数问题可以被改写为决策问题。例如，两个整数的乘法可以表示为三元组（a，b，c），这样关系a × b = c成立。决定一个给定的三元组是否是这个集合的一员相当于解决两个数相乘的问题。
===Measuring the size of an instance===
===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 2''n'' 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 2''n'' 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?
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?
为了衡量解决一个计算问题的难度，人们可能希望知道最佳算法需要多少时间来解决这个问题。但是，运行时间通常取决于实例。特别是，较大的实例将需要更多的时间来解决。因此，解决一个问题所需的时间（或所需的空间，或任何复杂程度的度量）被计算为实例大小的函数。这通常被认为是以位为单位的输入大小。复杂度理论关心的是算法如何随着输入大小的增加而伸缩。例如，在求一个图是否连通的问题中，一个2n个顶点的图比一个有n个顶点的图要多花多少时间？
==Machine models and complexity measures==
==Machine models and complexity measures机器模型与复杂性度量==
===Turing machine===
===Turing machine图灵机===
{{main|Turing machine}}
{{main|Turing machine}}
[[File:Turing machine 2b.svg|thumb|right|An illustration of a Turing machine]]
[[File:Turing machine 2b.svg|thumb|right|An illustration of a 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.
图灵机是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。图灵机器并不是一种实用的计算技术，而是一种计算机的通用模型，从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个图灵机器来解决这个问题。事实上，这就是教会图灵论点的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如RAM机器、Conway的生命游戏、元胞自动机或任何编程语言都可以在图灵机器上进行计算。由于图灵机易于数学分析，并且被认为与任何其他计算模型一样强大，图灵机是复杂性理论中最常用的模型。
===Other machine models===
===Other machine models其他机型===
Many machine models different from the standard [[Turing machine equivalents#Multi-tape Turing machines|multi-tape Turing machines]] have been proposed in the literature, for example [[random access machine]]s. 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.<ref>See {{harvnb|Arora|Barak|2009|loc=Chapter 1: The computational model and why it doesn't matter}}</ref> What all these models have in common is that the machines operate [[deterministic algorithm|deterministically]].
Many machine models different from the standard [[Turing machine equivalents#Multi-tape Turing machines|multi-tape Turing machines]] have been proposed in the literature, for example [[random access machine]]s. 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.<ref>See {{harvnb|Arora|Barak|2009|loc=Chapter 1: The computational model and why it doesn't matter}}</ref> What all these models have in common is that the machines operate [[deterministic algorithm|deterministically]].
===Complexity measures===
===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'')).
The complexity of an algorithm is often expressed using big O notation.
The complexity of an algorithm is often expressed using big O notation.
算法的复杂性通常用大 o 表示法来表示。
算法的复杂性通常用大 O 符号来表示。
===Best, worst and average case complexity===
===Best, worst and average case complexity最佳、最差和平均情况下的复杂度===
[[File:Sorting quicksort anim.gif|thumb|Visualization of the [[quicksort]] [[algorithm]] that has [[Best, worst and average case|average case performance]] <math>\mathcal{O}(n\log n)</math>.]]
[[File:Sorting quicksort anim.gif|thumb|Visualization of the [[quicksort]] [[algorithm]] that has [[Best, worst and average case|average case performance]] <math>\mathcal{O}(n\log n)</math>.]]
[[文件：排序快速排序动画.gif|thumb |可视化[[快速排序]][[算法]]，它具有[[最佳、最差和平均情况|平均情况性能]]<math>\mathcal{O}(n\log n)</math>.]]
Visualization of the [[quicksort algorithm that has average case performance <math>\mathcal{O}(n\log n)</math>.]]
Visualization of the [[quicksort algorithm that has average case performance <math>\mathcal{O}(n\log n)</math>.]]
[[具有平均大小写性能的快速排序算法 < math > mathcal { o }(n log n) </math > ]]
[[具有平均大小写性能的快速排序算法<math>\mathcal{O}(n\log n)</math>.]]
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:
===Upper and lower bounds on the complexity of problems===
===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'').
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).
对计算时间或类似的资源进行分类时，演示最有效算法解决给定问题所需的最大时间的上下界是很有帮助的。一个算法的复杂性通常被认为是其最坏情况的复杂性，除非另有说明。分析一个特定的算法属于算法分析的范畴。为了给出问题时间复杂度的上界 t (n) ，只需要给出一个运行时间最多为 t (n)的特定算法。然而，证明下界要困难得多，因为下界表明了解决给定问题的所有可能的算法。“所有可能的算法”这个短语不仅包括今天已知的算法，还包括将来可能发现的任何算法。为了给出问题 t (n)的下界，需要证明任何算法的时间复杂度都不能低于 t (n)。
对计算时间或类似的资源进行分类时，演示最有效算法解决给定问题所需的最大时间的上下界是很有帮助的。一个算法的复杂性通常被认为是其最坏情况的复杂性，除非另有说明。分析一个特定的算法属于算法分析的范畴。为了给出问题时间复杂度的上界 T(n) ，只需要给出一个运行时间最多为 T(n)的特定算法。然而，证明下界要困难得多，因为下界表明了解决给定问题的所有可能的算法。“所有可能的算法”这个短语不仅包括今天已知的算法，还包括将来可能发现的任何算法。为了给出问题T(n)的下界，需要证明任何算法的时间复杂度都不能低于 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) = 7n<sup>2</sup> + 15n + 40, in big O notation one would write T(n) = O(n<sup>2</sup>).
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) = 7n<sup>2</sup> + 15n + 40, in big O notation one would write T(n) = O(n<sup>2</sup>).
上下界通常使用大 o 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于使用的计算模型的具体细节。例如，如果 t (n) = 7n < sup > 2 </sup > + 15n + 40，在大 o 表示法中，人们会写 t (n) = o (n < sup > 2 </sup >)。
上下界通常使用大 O 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于使用的计算模型的具体细节。例如，如果 T(n) = 7n<sup>2</sup> + 15n + 40,在大O表示法中，人们会写T(n) = O(n<sup>2</sup>)。
==Complexity classes==
==Complexity classes复杂性类==
{{main|Complexity class}}
{{main|Complexity class}}
===Defining complexity classes===
===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 problem]]s, [[counting problem (complexity)|counting problem]]s, [[optimization problem]]s, [[promise problem]]s, etc.
* The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on [[function problem]]s, [[counting problem (complexity)|counting problem]]s, [[optimization problem]]s, [[promise problem]]s, etc.
*计算问题的类型：最常用的问题是决策问题。然而，复杂度类可以基于[[函数问题]]s、[[计数问题（复杂性）|计数问题]]s、[[优化问题]]s、[[承诺问题]]等定义。
* The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, [[Boolean circuit]]s, [[quantum Turing machine]]s, [[monotone circuit]]s, etc.
* The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, [[Boolean circuit]]s, [[quantum Turing machine]]s, [[monotone circuit]]s, etc.
*计算模型：最常见的计算模型是确定性图灵机，但许多复杂度类是基于非确定性图灵机，[[布尔电路]]s，[[量子图灵机]]s，[[单调电路]]s等。
* The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.
* The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.
*有界的资源和有界资源：这两个属性通常一起表述，如“多项式时间”、“对数空间”、“常数深度”等。
===Important complexity classes===
===Important complexity classes重要的复杂性类===
[[Image:Complexity subsets pspace.svg|thumb|right|A representation of the relation among complexity classes]]
[[Image:Complexity subsets pspace.svg|thumb|right|A representation of the relation among complexity classes]]
[[图：复杂性子集pspace.svg|thumb |右|表示复杂类之间的关系]]
A representation of the relation among complexity classes
A representation of the relation among complexity classes
===Hierarchy theorems===
===Hierarchy theorems层次定理===
{{main|time hierarchy theorem|space hierarchy theorem}}
{{main|time hierarchy theorem|space hierarchy theorem}}
===Reduction===
===Reduction约简===
{{main|Reduction (complexity)}}
{{main|Reduction (complexity)}}
==Important open problems==
==Important open problems重要的开放性问题==
[[Image:Complexity classes.svg|thumb|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.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] |volume=22|year=1975|pages=151–171|doi=10.1145/321864.321877|issue=1|postscript=.}}</ref>]]
[[Image:Complexity classes.svg|thumb|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.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] |volume=22|year=1975|pages=151–171|doi=10.1145/321864.321877|issue=1|postscript=.}}</ref>]]
[[图片：Complexity classes.svg|假设P≠NP的复杂性类的拇指图。在这种情况下，P和NP完全外的NP问题的存在性是由Ladner证明的。
===P versus NP problem===
===P versus NP problemP/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.
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.
===Problems in NP not known to be in P or NP-complete===
===Problems in NP not known to be in P or NP-completeNP中不知道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 <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> 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.
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 <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> 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'''.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in '''P''' or to be '''NP-complete'''.
It was shown by Ladner that if '''P''' ≠ '''NP''' then there exist problems in '''NP''' that are neither in '''P''' nor '''NP-complete'''.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in '''P''' or to be '''NP-complete'''.
Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-complete”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或“NP-complete”。
The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in '''P''', '''NP-complete''', or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation
[[图同构问题]]是确定两个有限[[图（离散数学）|图]]是否为[[图同构|同构]]的计算问题。复杂度理论中一个重要的未解决的问题是图的同构问题是在“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.
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.
| issue = 5
| issue = 5
==Intractability== <!-- This section is linked from Minimax, Intractability, Intractable -->
==Intractability难处理性== <!-- This section is linked from Minimax, Intractability, Intractable -->
= = 棘手 = = = < ! -- 本节链接于 minimax，棘手，棘手 -- >
= = 棘手 = = = < ! -- 本节链接于 minimax，棘手，棘手 -- >
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)|RSA]] algorithm. The integer factorization problem is in '''NP''' and in '''co-NP''' (and even in UP and co-UP<ref>{{cite web|first=Lance|last=Fortnow|authorlink=Lance Fortnow|title=Computational Complexity Blog: Factoring|date=2002-09-13|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html|website=weblog.fortnow.com}}</ref>). 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 <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> 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.
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)|RSA]] algorithm. The integer factorization problem is in '''NP''' and in '''co-NP''' (and even in UP and co-UP<ref>{{cite web|first=Lance|last=Fortnow|authorlink=Lance Fortnow|title=Computational Complexity Blog: Factoring|date=2002-09-13|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html|website=weblog.fortnow.com}}</ref>). 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 <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> 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.
[[整数因式分解问题]]是确定给定整数的[[素数因式分解]]的计算问题。作为一个决策问题，它是决定输入是否有一个素数因子小于“k”的问题。目前还没有有效的整数因式分解算法，这一事实构成了几种现代密码系统的基础，例如[[RSA（algorithm）| RSA]]算法。整数因式分解问题出现在“NP”和“co-NP”中（甚至在UP和co-UP<ref>{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|网站=博客.fortnow.com}}</ref>）。如果问题是“NP-complete”，则多项式时间层次将塌陷到其第一级（即，“NP”将等于“co-NP”）。最著名的整数因式分解算法是[[一般数域筛]]，它需要时间<math>O（e^{\left（\sqrt[3]{\frac{64}{9}\right）\sqrt[3]{（\logn）}\sqrt[3]{（\log\logn）^2}）</math><ref>Wolfram MathWorld:[http://mathworld.wolfram.com/NumberFieldSieve.html数字字段筛选]</ref>将奇数整数“n”作为因子。然而，这个问题最著名的[[量子算法]]，即[[Shor算法]]，确实在多项式时间内运行。不幸的是，这一事实并不能说明非量子复杂性类的问题所在。
However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.
However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.
===Separations between other complexity classes===
===Separations between other complexity classes其他复杂性类之间的分离===
To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2<sup>n</sup> operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10<sup>12</sup> operations each second, the program would run for about 4 × 10<sup>10</sup> years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001<sup>n</sup> operations is practical until n gets relatively large.
To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2<sup>n</sup> operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 10<sup>12</sup> operations each second, the program would run for about 4 × 10<sup>10</sup> years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001<sup>n</sup> 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 (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.
Many known complexity classes are suspected to be unequal, but this has not been proved. For instance '''P''' ⊆ '''NP''' ⊆ '''[[PP (complexity)|PP]]''' ⊆ '''PSPACE''', but it is possible that '''P''' = '''PSPACE'''. If '''P''' is not equal to '''NP''', then '''P''' is not equal to '''PSPACE''' either. Since there are many known complexity classes between '''P''' and '''PSPACE''', such as '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.
许多已知的复杂性类被怀疑是不相等的，但这一点尚未得到证实。例如''P''''''NP'''''[[PP（complexity）|⊆'''''''PSPACE''，但是''P'''=''PSPACE'''。如果“P”不等于“NP”，那么“P”也不等于“PSPACE”。由于在''P''和''PSPACE''之间有许多已知的复杂度类别，例如''RP''、''BPP''、''PP''、''BQP''、''MA''、''PH''等，所以所有这些复杂度类别都有可能塌陷为一个类别。证明这些类中的任何一个是不相等的，这将是复杂性理论的一个重大突破。
Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n<sup>15</sup>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n<sup>3</sup> or n<sup>2</sup> algorithms are often impractical on realistic sizes of problems.
Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n<sup>15</sup>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n<sup>3</sup> or n<sup>2</sup> algorithms are often impractical on realistic sizes of problems.
Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''. Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.
Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''. Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.
“是的，问题的答案与‘NP’的问题是相反的。据信<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/博阿斯·巴拉克关于计算复杂性的课程][http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf“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.
同样地，也不知道“L”（对数空间中可以解决的所有问题的集合）是严格包含在“P”中还是等于“P”。同样，在这两者之间有许多复杂的类，例如''NL''和''NC''，并且不知道它们是不同的类还是相等的类。
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.
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'''.
It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.
有人怀疑“P”和“BPP”是相等的。但是，如果'''BPP'''=''NEXP''，它当前是打开的。
Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.
Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.
==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->
==Intractability难解性== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] 本节链接自[[Minimax]]、[[难处理性]]、[[棘手]]-->
{{See also|Combinatorial explosion}}
{{See also|Combinatorial explosion}}
A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}””。<ref>Hopcroft，J.e.，Motwani，R.和Ullman，J.D.（2007）[[自动机理论导论，语言，而计算]]，Addison-Wesley，Boston/San-Francisco/newyork（第368页）</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.
Tractable problems are frequently identified with problems that have polynomial-time solutions ('''P''', '''PTIME'''); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If NP is not the same as P, then [[NP-hard]] problems are also intractable in this sense.
Tractable problems are frequently identified with problems that have polynomial-time solutions ('''P''', '''PTIME'''); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If NP is not the same as P, then [[NP-hard]] problems are also intractable in this sense.
可处理问题通常与具有多项式时间解的问题（''P''，''PTIME''）；这被称为[[Cobham–Edmonds thesis]]。在这个意义上，已知的棘手问题包括[[EXPTIME]]-困难的问题。如果NP与P不同，那么[[NP-hard]]问题在这个意义上也是难以解决的。
In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.
In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.
However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].
However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].
然而，这种辨识是不精确的：具有大阶数或大超前系数的多项式时间解增长很快，对于实际的规模问题可能是不切实际的；相反，缓慢增长的指数时间解在实际输入上可能是实际的，或者在最坏情况下需要很长时间的解可能需要很短的时间时间在大多数情况下还是一般情况下，因此还是实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，[[Presburger algorithm]]中的决策问题已被证明不在P中，但在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次时间的大范围内解决NP完全[[背包问题]]，并且[[SAT solver]]通常处理NP完全[[布尔可满足性问题]]的大型实例。
To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2<sup>''n''</sup> operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10<sup>12</sup> operations each second, the program would run for about 4 × 10<sup>10</sup> years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001<sup>''n''</sup> operations is practical until ''n'' gets relatively large.
To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2<sup>''n''</sup> operations before halting. For small ''n'', say 100, and assuming for the sake of example that the computer does 10<sup>12</sup> operations each second, the program would run for about 4 × 10<sup>10</sup> years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001<sup>''n''</sup> operations is practical until ''n'' gets relatively large.
要了解为什么指数时间算法在实际中通常不可用，请考虑一个在停止之前进行2次<sup>“n'</sup>操作的程序。对于小的“n”，比如100，假设计算机每秒进行10次<sup>12次</sup>操作，程序将运行大约4×10<sup>10</sup>年，与[[宇宙年龄]]的数量级相同。即使有一台速度快得多的计算机，该程序也只对非常小的实例有用，从这个意义上说，一个问题的棘手程度在某种程度上与技术进步无关。然而，在“n”变得相对较大之前，需要1.0001<sup>“n”</sup>运算的指数时间算法是可行的。
Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ''n''<sup>15</sup>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ''n''<sup>3</sup> or ''n''<sup>2</sup> algorithms are often impractical on realistic sizes of problems.
Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ''n''<sup>15</sup>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ''n''<sup>3</sup> or ''n''<sup>2</sup> algorithms are often impractical on realistic sizes of problems.
类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”<sup>15</sup>，那么认为它是有效的是不合理的，而且除了在小实例上，它仍然是无用的。实际上，在实践中，即使是“n”<sup>3</sup>或“n”<sup>2</sup>算法对于实际大小的问题往往是不切实际的。
==Continuous complexity theory连续复杂性理论==
==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<ref>{{cite journal | title = Complexity Theory and Numerical Analysis | id = {{citeseerx|10.1.1.33.4678}} | first = Steve | last = Smale | journal = Acta Numerica | volume = 6 | pages = 523–551 | year = 1997 | publisher = Cambridge Univ Press | doi = 10.1017/s0962492900002774 | bibcode = 1997AcNum...6..523S }}</ref> is [[information based complexity]].
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<ref>{{cite journal | title = Complexity Theory and Numerical Analysis | id = {{citeseerx|10.1.1.33.4678}} | first = Steve | last = Smale | journal = Acta Numerica | volume = 6 | pages = 523–551 | year = 1997 | publisher = Cambridge Univ Press | doi = 10.1017/s0962492900002774 | bibcode = 1997AcNum...6..523S }}</ref> is [[information based complexity]].
连续复杂性理论可以指问题的复杂性理论，这些问题涉及通过离散化近似的连续函数，如[[数值分析]]中所研究的那样。数值分析复杂性理论的一种方法是[[基于信息的复杂性]]。
Continuous complexity theory can also refer to complexity theory of the use of [[analog computation]], which uses continuous [[dynamical system]]s and [[differential equation]]s.<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref> [[Control theory]] can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>
Continuous complexity theory can also refer to complexity theory of the use of [[analog computation]], which uses continuous [[dynamical system]]s and [[differential equation]]s.<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref> [[Control theory]] can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>
连续复杂性理论也可以参考复杂性理论中使用的[[模拟计算]]，它使用连续的[[动力系统]]和[[微分方程]]s。[[控制理论]]可以看作是一种计算形式，微分方程用于连续时间和混合离散连续时间系统的建模。
==History历史==
==History==
An early example of algorithm complexity analysis is the running time analysis of the [[Euclidean algorithm]] done by [[Gabriel Lamé]] in 1844.
An early example of algorithm complexity analysis is the running time analysis of the [[Euclidean algorithm]] done by [[Gabriel Lamé]] in 1844.
算法复杂性分析的一个早期例子是1844年[[Gabriel Lamé]]对[[Euclidean algorithm]]的运行时间分析。
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by [[Alan Turing]] in 1936, which turned out to be a very robust and flexible simplification of a computer.
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by [[Alan Turing]] in 1936, which turned out to be a very robust and flexible simplification of a computer.
在明确致力于算法问题复杂性的实际研究开始之前，各种研究人员已经奠定了大量的基础。其中最具影响力的是1936年[[Alan Turing]]对图灵机器的定义，这是一种非常健壮和灵活的计算机简化。
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.<ref name="Fortnow 2003">{{Harvtxt|Fortnow|Homer|2003}}</ref> In addition, in 1965 [[Jack Edmonds|Edmonds]] suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.<ref>Richard M. Karp, "[http://cecas.clemson.edu/~shierd/Shier/MthSc816/turing-karp.pdf Combinatorics, Complexity, and Randomness]", 1985 Turing Award Lecture</ref>
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.<ref name="Fortnow 2003">{{Harvtxt|Fortnow|Homer|2003}}</ref> In addition, in 1965 [[Jack Edmonds|Edmonds]] suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.<ref>Richard M. Karp, "[http://cecas.clemson.edu/~shierd/Shier/MthSc816/turing-karp.pdf Combinatorics, Complexity, and Randomness]", 1985 Turing Award Lecture</ref>
系统地研究计算复杂性的开端，要归功于1965年[[Juris Hartmanis]]和[[Richard E.Stearns]]的开创性论文《算法的计算复杂性》，提出了[[时间复杂度]]和[[空间复杂度]]的定义，并证明了层次定理。
Earlier papers studying problems solvable by Turing machines with specific bounded resources include<ref name="Fortnow 2003"/> [[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<ref>{{Cite journal | last1 = Yamada | first1 = H. | title = Real-Time Computation and Recursive Functions Not Real-Time Computable | journal = IEEE Transactions on Electronic Computers | volume = EC-11 | issue = 6 | pages = 753–760 | year = 1962 | doi = 10.1109/TEC.1962.5219459}}</ref> on real-time computations (1962). Somewhat earlier, [[Boris Trakhtenbrot]] (1956), a pioneer in the field from the USSR, studied another specific complexity measure.<ref>Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski
早期研究图灵机器在特定有界资源下可解问题的论文包括{{Cite journal | last1=Yamada | first1=H.| title=实时计算和递归函数不可实时计算| journal=IEEE电子计算机事务|卷=EC-11 |问题=6 |页=753-760 |年=1962 | doi=10.1109/TEC.1962.5219459}}
Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (in Russian)</ref> As he remembers:
Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (in Russian)</ref> As he remembers:
In 1967, [[Manuel Blum]] formulated a set of [[axiom]]s (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 [[Blum's speedup theorem|speed-up theorem]]. The field began to flourish in 1971 when the [[Stephen Cook]] and [[Leonid Levin]] [[Cook–Levin theorem|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 [[combinatorics|combinatorial]] and [[graph theory|graph theoretical]] problems, each infamous for its computational intractability, are NP-complete.<ref>{{Citation | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | title = Complexity of Computer Computations |editor= R. E. Miller |editor2=J. W. Thatcher| publisher = New York: Plenum | pages = 85–103 | year = 1972}}</ref>
In 1967, [[Manuel Blum]] formulated a set of [[axiom]]s (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 [[Blum's speedup theorem|speed-up theorem]]. The field began to flourish in 1971 when the [[Stephen Cook]] and [[Leonid Levin]] [[Cook–Levin theorem|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 [[combinatorics|combinatorial]] and [[graph theory|graph theoretical]] problems, each infamous for its computational intractability, are NP-complete.<ref>{{Citation | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | title = Complexity of Computer Computations |editor= R. E. Miller |editor2=J. W. Thatcher| publisher = New York: Plenum | pages = 85–103 | year = 1972}}</ref>
1967年，[[Manuel Blum]]提出了一组[[公理]]s（现在称为[[Blum axioms]]），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的[[Blum加速定理|加速定理]]。这个领域在1971年开始蓬勃发展，当时[[Stephen Cook]]和[[Leonid Levin]][[Cook–Levin定理|证明了[[NP complete]]实际相关问题的存在。1972年，[[Richard Karp]]以其里程碑式的论文《组合问题中的可还原性》（Reductibility In Combinational Problems）将这一想法向前推进了一大步，在这篇论文中，他展示了21个不同的[[组合学|组合]]和[[图论|图论]]问题，每一个都因其计算难处理而臭名昭著，是NP完全的。<ref>{引文{author=Richard M.Karp | chapter=组合问题之间的可约性|章url=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf|title=计算机计算的复杂性
In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case{{cn|reason=passive, no source|date=August 2019}}, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>
In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case{{cn|reason=passive, no source|date=August 2019}}, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>
20世纪80年代，人们对NP完全问题的平均困难度和近似解做了大量的工作。当时，计算复杂性理论处于鼎盛时期，人们普遍认为，如果一个问题最终证明是NP完全的，那么在实际情况下处理该问题的可能性很小。然而，越来越清楚的是，{cn | reason=passive，no source | date=2019年8月}的情况并不总是如此，一些作者声称，对于实践中出现的典型问题，一般渐近结果往往不重要。
==See also又及==
==See also==
{{Div col|colwidth=25em}}
{{Div col|colwidth=25em}}
* [[Context of computational complexity]]
* [[Context of computational complexity]]
*[[计算复杂性的上下文]]
| last2=Barak | first2=Boaz
| last2=Barak | first2=Boaz
系列 = 计算机科学专著
系列 = 计算机科学专著
=== Citations ===
=== Citations 引用===
}}
}}
| last = Du
| last = Du
===Textbooks===
===Textbooks教材===
| first=Ding-Zhu
| first=Ding-Zhu
<small>This page was moved from [[wikipedia:en:Computational complexity theory]]. Its edit history can be viewed at [[计算复杂性理论/edithistory]]</small></noinclude>
<small>This page was moved from [[wikipedia:en:Computational complexity theory]]. Its edit history can be viewed at [[计算复杂性理论/edithistory]]</small></noinclude>
<small>此页摘自[[维基百科：英语：计算复杂性理论]]。其编辑历史记录可在[[编辑历史记录]上查看</small></noinclude>
[[Category:待整理页面]]
[[Category:待整理页面]]