4
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由水流心不竞初译，翻译字数共，未经审校，带来阅读不便，请见谅。+ 第5行：
第5行： − [[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]].+ − − [[计算复杂性]]理论关注于根据资源使用情况对[[计算问题]]进行分类，并将这些类相互关联。计算问题是可由计算机解决的任务。计算问题可以通过机械地应用数学步骤来解决，例如[[算法]]。 − + − + − − 如果一个问题的解决需要大量的资源，无论使用什么算法，那么这个问题本身就被认为是困难的。该理论通过引入数学的'''<font color="#ff8000"> 计算模型Models of computation</font>'''来研究这些问题，并量化它们的'''<font color="#ff8000"> 计算复杂性</font>'''，即解决这些问题所需的资源量，如时间和存储量，将这种直觉形式化。其他复杂性的度量也被使用，例如通信量(用于'''<font color="#ff8000"> 通信复杂性</font>''') ，电路中的逻辑门数(用于'''<font color="#ff8000"> 电路复杂性</font>''')和处理器数(用于'''<font color="#ff8000"> 并行计算</font>''')。'''<font color="#ff8000"> 计算复杂性理论</font>'''的一个作用是确定计算机能做什么和不能做什么的实际限制。'''<font color="#ff8000"> P/NP问题</font>'''致力于计算复杂性领域，是七大'''<font color="#ff8000"> 千禧年奖问题Millennium Prize Problems</font>'''之一。+ + − + − − − 理论计算机科学中与其密切相关的领域是'''<font color="#ff8000"> 算法分析Analysis of algorithms</font>'''和'''<font color="#ff8000"> 可计算性理论Computability theory</font>'''。<font color="#ff8000"> 算法分析</font>和<font color="#ff8000"> 计算复杂性理论</font>的一个关键区别在于前者致力于分析一个特定算法解决问题所需的资源量，而后者则提出了一个更普遍的问题，关于所有可能用于解决同一问题的算法的。更准确地说，<font color="#ff8000"> 计算复杂性理论</font>试图对那些能够或不能够用适当限制的资源来解决的问题进行分类。反过来，对可用资源施加限制是区分计算复杂性和可计算性理论的关键: 后者的理论提出，原则上，什么样的问题可以通过算法来解决。+ − − − − ==Computational problems计算问题== − [[Image:TSP Deutschland 3.png|thumb|upright=1.5|A traveling salesman tour through 14 German cities.]]+ − [[图片：TSP Deutschland3.png |拇指|直立=1.5 |旅行推销员在14个德国城市旅行。]]+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − 一个旅行推销员游览了14个德国城市。+ − + − ===Problem instances问题实例===+ − − − 一个'''<font color="#ff8000"> 计算问题</font>'''可以被看作是一个实例的无限集合和每个实例的解决方案。'''<font color="#ff8000"> 计算问题</font>'''的输入字符串被称为问题实例，不应与问题本身混淆。在计算复杂性理论，问题指的是要解决的抽象问题。相比之下，这个问题的实例是一个相当具体的表述，可以作为决策问题的输入。例如，考虑素性测试的问题。实例是一个数字(例如，15) ，如果数字是质数，解决方案是“是” ，否则是“否”(在这种情况下，15不是质数，答案是“否”)。换句话说，实例是问题的特定输入，解决方案是与给定输入对应的输出。+ + − + − To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.+ − 为了进一步突出问题和实例之间的区别，考虑以下关于旅行推销员问题的决策版本: 是否有一条最多2000公里的路线穿过德国所有15个最大的城市？这个特殊问题的定量答案对于解决这个问题的其他实例没有什么用处，例如要求在米兰的所有地点进行往返旅行，这些地点的总长度最多不超过10公里。基于这个原因，'''<font color="#ff8000"> 复杂性理论</font>'''解决的是'''<font color="#ff8000"> 计算问题</font>'''而不是特定的问题实例。 − + − + − ===Representing problem instances问题表达实例=== − − − 在考虑'''<font color="#ff8000"> 计算问题</font>'''时，一个问题实例是字母表上的字符串。通常，字母表被认为是二进制字母表(即集合{0,1}) ，因此字符串是位字符串。在现实世界的计算机中，除了位字符串以外的数学对象必须进行适当的编码。例如，整数可以用二进制表示法表示，图可以通过它们的'''<font color="#ff8000"> 邻接矩阵</font>'''直接进行编码，或者用二进制编码它们的'''<font color="#ff8000"> 邻接列表</font>'''。+ − 第73行：
第91行： − 尽管复杂性理论定理的一些证明通常假设输入编码的某些具体选择，但是有人试图使讨论足够抽象，使其与编码的选择无关。这可以通过确保不同的表示可以有效地相互转换来实现。+ + + + + − ===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.]]+ − [[图：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.]] − − 一个[[决策问题对任何输入只有两个可能的输出，是或否(或者交替1或0)]] − − [[Decision problem]]s are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either ''yes'' or ''no'', or alternately either 1 or 0. A decision problem can be viewed as a [[formal language]], where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an [[algorithm]], whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer ''yes'', the algorithm is said to accept the input string, otherwise it is said to reject the input. − '''<font color="#ff8000"> 决策问题Decision problems</font>'''是计算复杂性理论研究的中心内容之一。'''<font color="#ff8000"> 决策问题</font>'''是一种特殊类型的计算问题，其答案要么是“是”，要么是“否”，要么是“1”或“0”。'''<font color="#ff8000"> 决策问题</font>'''可以看作是一种形式语言，语言的成员是输出为“是”的实例，而非成员是输出为“否”的实例，其目的是借助算法来确定给定的输入字符串是否是所考虑的形式语言的成员。如果决定这个问题的算法返回的答案是“是”，则表示该算法接受输入字符串，否则表示拒绝输入。+ − + − '''<font color="#ff8000"> 决策问题</font>'''的一个例子如下。输入是一个任意的'''<font color="#ff8000"> 图</font>'''。问题是判断给定的图是否连通。与这个决策问题相关的形式语言是所有连通图的集合ーー为了获得这种语言的精确定义，必须决定<font color="#ff8000"> 图</font>是如何编码成二进制字符串的。+ − ===Function problems函数问题===+ − + − − '''<font color="#ff8000"> 函数问题</font>'''是一个计算问题，其中每个输入都有一个输出（'''<font color="#ff8000"> 总函数</font>'''），但输出比'''<font color="#ff8000"> 决策问题</font>'''更复杂，即输出不只是是或否。值得注意的例子包括'''<font color="#ff8000"> 旅行商问题</font>'''和'''<font color="#ff8000"> 整数因式分解问题</font>'''。+ − + − + − 人们很容易认为'''<font color="#ff8000"> 函数问题</font>'''的概念比'''<font color="#ff8000"> 决策问题</font>'''的概念丰富得多。然而，事实并非如此，因为函数问题可以被改写为决策问题。例如，两个整数的乘法可以表示为三元组（a, b, c），这样关系a × b = c成立。决定一个给定的三元组是否是这个集合的一员相当于解决两个数相乘的问题。+ − + − ===Measuring the size of an instance测量实例的大小===+ − − − 为了衡量解决一个计算问题的难度，人们可能希望知道最佳算法需要多少时间来解决这个问题。但是，运行时间通常取决于具体实例。特别是，较大的实例将需要更多的时间来解决。因此，解决一个问题所需的时间（或所需的空间，或任何复杂程度的度量）被计算为关于实例规模的函数。这通常被认为是以比特为单位的输入大小。复杂度理论关心的是算法如何随着输入大小的增加而变化。例如，在求一个图是否连通的问题中，一个2n个顶点的图比一个有n个顶点的图要多花多少时间？+ − + − − + − ==Machine models and complexity measures机器模型与复杂性度量==+ − + − + − + − ===Turing machine图灵机===+ − + − {{main|Turing machine}} − − [[File:Turing machine 2b.svg|thumb|right|An illustration of a Turing machine]] − [[文件：图灵机器2b.svg |拇指|右|图灵机器图解]] 第148行：
第156行： − + − + − + − 许多类型的'''<font color="#ff8000"> 图灵机Turing machine</font>'''被用来定义复杂性类，如'''<font color="#ff8000"> 确定性图灵机、概率图灵机、不确定图灵机、量子图灵机、对称图灵机和交替图灵机</font>'''。它们在原则上都同样强大，但当资源(如时间或空间)被限制时，其中一些可能比其他的更强大。+ − + − − '''<font color="#ff8000"> 确定性图灵机Turing machine</font>'''是最基本的图灵机，它使用一组固定的规则来决定未来的动作。'''<font color="#ff8000"> 概率图灵机Probabilistic Turing machine</font>'''是一种具有额外随机位的确定性图灵机。做出概率决策的能力通常有助于算法更有效地解决问题。使用随机位的算法称为'''<font color="#ff8000">随机算法</font>'''。'''<font color="#ff8000"> 非确定型图灵机Non-deterministic Turing machine</font>'''是一种确定性图灵机，具有额外的非确定性特征，它允许图灵机在给定的状态下有多种可能的未来动作。查看非确定性的一种方法是，图灵机在每个步骤中分支成许多可能的计算路径，如果它在这些分支的任何一个中解决了这个问题，就说它已经解决了这个问题。显然，这个模型并不意味着是一个物理上可实现的模型，它只是一个理论上有趣的抽象机器，它产生了特别有趣的复杂性类。例如，请参阅 '''<font color="#ff8000"> 非确定性算法Non-deterministic algorithm</font>'''。+ − ===Other machine models其他机型===+ − + − − 文献中提出了许多不同于标准的多带'''<font color="#ff8000">图灵机 </font>'''的机器模型，例如'''<font color="#ff8000"> 随机存取机Random access machine</font>'''。也许令人惊讶的是，这些模型中的每一个都可以转换成另一个模型，而不需要提供任何额外的计算能力。这些替代模型的时间和内存消耗可能会有所不同。所有这些模型的共同点是，这些机器都是以确定的方式运行的。+ − + − − 然而，一些计算问题更容易用更多不寻常的资源来分析。例如，'''<font color="#ff8000">非确定型图灵机 </font>'''是一个允许同时检查许多不同可能性的计算模型。'''<font color="#ff8000">非确定型图灵机 </font>'''对我们物理上想要的计算算法没有什么影响，但是它的分支精确地捕获了我们想要分析的许多数学模型，因此'''<font color="#ff8000">非确定性时间 </font>'''是分析计算问题的一个非常重要的资源。+ − ===Complexity measures复杂性度量===+ − + − − 为了精确定义在给定的时间和空间内解决问题的意义，我们使用了'''<font color="#ff8000">确定性图灵机 </font>'''这样的计算模型。确定性图灵机 M 在输入 x 上所需的时间是该机在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 M 对每个长度 n 的输入所需的时间最多为 f (n) ，则称 M 在时间 f (n)内运行。如果存在一个在时间 f (n)内运行的图灵机，决策问题 A 就可以在时间 f (n)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在<font color="#ff8000">确定性图灵机 </font>上，在时间 f (n)内可解决的问题的集合由 '''<font color="#ff8000"> DTIME(f (n))</font>'''表示。+ − + − − 可以对空间要求作类似的定义。虽然时间和空间是最著名的复杂性资源，但任何'''<font color="#ff8000"> 复杂性度量Complexity measure</font>'''都可以被视为计算资源。复杂性度量通常是由 '''<font color="#ff8000"> 布鲁姆复杂性公理Blum complexity axioms</font>'''定义的。复杂性理论中使用的其他复杂性度量包括'''<font color="#ff8000">通信复杂性、电路复杂性和决策树复杂性</font>'''。+ − + − − 算法的复杂性通常用大 O 符号来表示。+ − ===Best, worst and average case complexity最佳、最差和平均情况下的复杂度===+ + + + − + − [[文件：排序快速排序动画.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>.]] − [[具有平均大小写性能的快速排序算法<math>\mathcal{O}(n\log n)</math>.]]+ − − − '''<font color="#ff8000"> 最佳、最差和平均情况复杂度</font>'''是指用三种不同的方法来度量相同大小的不同输入的时间复杂度(或任何其他复杂度度量)。由于一些 n 大小的输入可能比其他的更快解决，我们定义了以下复杂性:+ − + − #Best-case complexity: This is the complexity of solving the problem for the best input of size ''n''. − − '''<font color="#ff8000"> 最佳情况复杂性Best-case complexity</font>''': 这就是解决n大小的最佳输入问题的复杂性。+ − − #Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a [[probability distribution]] over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size ''n''. + − '''<font color="#ff8000"> 平均案例复杂度Average-case complexity</font>''': 这是解决问题的平均复杂度。这种复杂性仅仅定义在输入的概率分布上。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小为 n 的所有输入的均匀分布来定义平均案例复杂度。+ − − #[[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''. + − '''<font color="#ff8000"> 最坏情况复杂度Worst-case complexity</font>''': 这是解决大小 n 的最坏输入问题的复杂度。+ − + − 成本由低到高的顺序是：最佳、平均（离散均匀分布）、摊销、最差。+ − + − + − + − ===Upper and lower bounds on the complexity of problems问题复杂性的上下界===+ − + − − 对计算时间或类似的资源进行分类时，演示最有效算法解决给定问题所需的最大时间的上下界是很有帮助的。一个算法的复杂性通常被认为是其最坏情况的复杂性，除非另有说明。分析一个特定的算法属于'''<font color="#ff8000"> 算法分析Analysis of algorithms</font>'''的范畴。为了给出问题时间复杂度的上界 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>).+ − 上下界通常使用大 O 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于使用的计算模型的具体细节。例如，如果 T(n) = 7n<sup>2</sup> + 15n + 40,在大O表示法中，人们会写T(n) = O(n<sup>2</sup>)。+ + − ==Complexity classes复杂性类==+ − + − {{main|Complexity class}} − − − − ===Defining complexity classes定义复杂性类=== − − − 复杂性类是一组相关的复杂性问题。更简单的复杂类由以下因素定义:+ − − * 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. − *计算问题的类型：最常用的问题是'''<font color="#ff8000"> 决策问题</font>'''。然而，复杂度类可以基于[[函数问题]]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. − *计算模型：最常见的计算模型是'''<font color="#ff8000"> 确定性图灵机</font>'''，但许多复杂度类是基于'''<font color="#ff8000"> 非确定性图灵机</font>'''，[[布尔电路]]s，[[量子图灵机]]s，[[单调电路]]s等。 − * The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc. − *有界的资源（或资源组）和有界资源：这两个属性通常一起表述，如'''<font color="#ff8000"> “多项式时间”、“对数空间”、“常数深度”</font>'''等。 + + + + + + 第302行：
第291行： − 一些复杂性类的复杂定义不适合这个框架。因此，一个典型的复杂性类的定义如下:+ − + − :The set of decision problems solvable by a deterministic Turing machine within time ''f''(''n''). (This complexity class is known as DTIME(''f''(''n'')).) − − + − + − − 但是通过一些具体的函数 f (n)来限定上面的计算时间通常会产生依赖于所选择的机器模型的复杂类。例如，语言{ xx | x 是任意二进制字符串}可以在多带图灵机上用线性时间求解，但在单带图灵机模型中需要二次时间。如果我们允许运行时间的多项式变化，Cobham-Edmonds 理论指出，”任何两个合理的和一般的计算模型的时间复杂性是多项式相关的”。这就形成了复杂度等级 P 的基础，P 是一组<font color="#ff8000">决策问题 </font>，可以由<font color="#ff8000">确定性图灵机 </font>在<font color="#ff8000">多项式时间 </font>内解决。相应的一组函数问题是 FP。+ − ===Important complexity classes重要的复杂性类===+ − + − + − + − [[Image:Complexity subsets pspace.svg|thumb|right|A representation of the relation among complexity classes]] − [[图：复杂性子集pspace.svg|thumb |右|表示复杂类之间的关系]] − 复杂类间关系的一种表示方法+ 第335行：
第319行： − 许多重要的复杂度类可以通过限定算法使用的时间或空间来定义。以这种方式定义的决策问题的一些重要的复杂性类别如下:+ − − {| − − {| − − {| − − |-style="vertical-align:top;" − − |-style="vertical-align:top;" − − |-style = “ vertical-align: top; ” − − | − − | − − | − − {| class="wikitable" − − {| class="wikitable" − + − |-+ − + − |-+ − − |- − − ! Complexity class − − ! Complexity class − − !复杂性类 − − ! Model of computation − − ! Model of computation − − !计算模式 − − ! Resource constraint − − ! Resource constraint − − !资源限制 − − |- − − |- − − |- − − ! colspan="3" | Deterministic time − − ! colspan="3" | Deterministic time − − !Colspan = “3” | 确定性时间 − − |- − − |- − − |- − − | [[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 (complexity)|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(2<sup>poly(''n'')</sup>) − − | Time O(2<sup>poly(n)</sup>) − − | Time o (2 < sup > poly (n) </sup >) − − |- − − |- − − |- − − ! colspan="3" | Non-deterministic time − − ! colspan="3" | Non-deterministic time − − !Colspan = “3” | 不确定时间 − − |- − − |- − − |- − − | [[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 (complexity)|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(2<sup>poly(''n'')</sup>)+ − − | Time O(2<sup>poly(n)</sup>) − − | Time o (2 < sup > poly (n) </sup >) − − |- − − |- − − |- − − |} − − |} − − |} − − | − − | − − | − − {| class="wikitable" − − {| class="wikitable" − + − |-+ − − |- − − |- − − − − ! Complexity class − − ! Complexity class − − !复杂性类 − − − − ! Model of computation − − ! Model of computation − − !计算模式 − − − − ! Resource constraint − − ! Resource constraint − − !资源限制 − − |- − − |- − − |- − − ! colspan="3" | Deterministic space − − ! colspan="3" | Deterministic space − − !Colspan = “3” | 确定性空间 − − |- − − |- − − |- − − | [[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 (complexity)|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(2<sup>poly(''n'')</sup>) − − | Space O(2<sup>poly(n)</sup>) − − | 空间 o (2 < sup > poly (n) </sup >) − − |- − − |- − − |- − − ! colspan="3" | Non-deterministic space − − ! colspan="3" | Non-deterministic space − − !Colspan = “3” | 非确定性空间 − − |- − − |- − − |- − − | [[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 (complexity)|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(2<sup>poly(''n'')</sup>)+ − | Space O(2<sup>poly(n)</sup>) − | 空间 o (2 < sup > poly (n) </sup >) − − |- − − |- − − |- − − |} − − |- − − |- − − |- − − |} − − |} − − |} − 第904行：
第401行： − + − − + − + − − 其他重要的复杂性类别包括 BPP、 ZPP 和 RP，它们使用'''<font color="#ff8000"> 概率图灵机</font>'''定义; AC 和 NC，它们使用'''<font color="#ff8000"> 布尔电路</font>'''定义; BQP 和 QMA，它们使用'''<font color="#ff8000"> 量子图灵机</font>'''定义。# p 是计数问题(不是决策问题)的一个重要的复杂类。类如 IP 和 AM 使用交互式证明系统定义。ALL 是所有决策问题的类别。+ − ===Hierarchy theorems层次定理===+ + + − {{main|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(''n''<sup>2</sup>), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.+ − For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME(n) is contained in DTIME(n<sup>2</sup>), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved. − 对于以这种方式定义的复杂类，我们希望证明放宽对计算时间的要求确实定义了更多的问题。特别是，虽然 DTIME (n)包含在 DTIME (n < sup > 2 </sup >)中，但是知道是否严格包含还是很有意思的。对于时间和空间要求，分别用时间和空间'''<font color="#ff8000">层次定理 </font>'''给出了这些问题的答案。它们之所以被称为'''<font color="#ff8000">层次定理 </font>'''，是因为它们通过约束各自的资源，在定义的类上生成一个适当的层次结构。因此，存在成对的复杂类，一个类可以被正确地包含在另一个类中。通过已经推导出了这种适当的包含集合，我们可以继续进行定量的陈述，说明需要多少额外的时间或空间才能增加可以解决的问题的数量。+ − − − − − + − :<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.+ − + − <math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>. + − + − − + − − :<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>. − − <math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>. + + 第961行：
第450行： − '''<font color="#ff8000"> 时间和空间层谱定理</font>'''构成了大多数复杂类分离结果的基础。例如，时间层谱定理告诉我们P严格包含在EXPTIME中，而空间层谱定理告诉我们L严格包含在PSPACE中。+ − ===Reduction简化===+ − + − {{main|Reduction (complexity)}}+ − − − 许多复杂性类是使用化简的概念来定义的。化简是将一个问题转化为另一个问题。它抓住了一个非正式的概念，即一个问题最多和另一个问题一样困难。例如，如果一个问题 x 可以用 y 的算法来解决，那么 x 并不比 y 困难，我们说 x 可简化为 y。根据简化方法，简化有多种类型，如 Cook 简化、 Karp 简化和 Levin 简化，以及简化复杂度的界限，如多项式时间简化或对数空间简化。+ − 第979行：
第465行： − 最常用的简化是'''<font color="#ff8000"> 多项式时间图灵归约Polynomial-time reduction</font>'''。这意味着还原过程需要'''<font color="#ff8000"> 多项式时间</font>'''。例如，将一个整数平方的问题可以简化为两个整数相乘的问题。这意味着两个整数相乘的算法可以用来求一个整数的平方。实际上，这可以通过给乘法算法的两个输入提供相同的输入来实现。因此我们看到平方并不比乘法困难，因为平方可以简化为乘法。+ − + − 这就产生了一个对于复杂类来说很难解决的问题的概念。如果C中的每一个问题都可以归结为X，那么对于一类问题C来说，问题X是困难的。因此，在C中没有问题比X更难，因为X的算法允许我们在C中解决任何问题。硬问题的概念取决于所用的简化类型。对于大于P的复杂度类，通常使用'''<font color="#ff8000"> 多项式时间图灵归约</font>'''。特别是NP的难问题集就是'''<font color="#ff8000"> NP难问题</font>'''集。+ − − If a problem ''X'' is in ''C'' and hard for ''C'', then ''X'' is said to be ''[[complete (complexity)|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, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. 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.<ref name="Sipser2006"/> − + − 如果一个问题X在C中并且对于C来说是难问题，那么X对于C来说是完全的。这意味着X是C中最难的问题（因为许多问题可能同样困难，我们可以说X是C中最难的问题之一），因此'''<font color="#ff8000"> 非确定性多项式时间复杂性类完全问题（NP完全问题）</font>'''类包含了NP中最困难的问题，从某种意义上说，它们是可能不在P中的最困难的问题。因为问题P = NP未被解决，如果能够将已知的NP完全问题Π<sub>2</sub>简化为另一个问题Π<sub>1</sub>，则表明Π<sub>1</sub>没有已知的多项式时间解。这是因为Π<sub>1</sub>的多项式时间解会产生Π<sub>2</sub>的多项式时间解。同样，由于所有NP问题都可以归结为集合，找到一个可以在多项式时间内解决的'''<font color="#ff8000"> NP完全问题</font>'''意味着P = NP。]]+ − + − [[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 problemP/NP问题=== + − 复杂度类P通常被视为一种数学抽象，用于建模那些允许有效算法的计算任务。这个假设被称为'''<font color="#ff8000"> 科巴姆-埃德蒙兹论Cobham–Edmonds thesis</font>'''。另一方面，复杂度类NP包含了许多人们想要有效解决的问题，但是没有有效的算法，例如'''<font color="#ff8000"> 布尔可满足性问题、哈密顿路径问题和顶点覆盖问题</font>'''。由于确定性图灵机是一种特殊的非确定性图灵机，因此很容易观察到P中的每个问题也是NP类的成员。+ − − − {{Main|P versus NP problem}} + − + − + − − 复杂度类P通常被视为一种数学抽象，用于建模那些允许有效算法的计算任务。这个假设被称为[[Cobham-Edmonds论文]]。另一方面，复杂度类[[NP（复杂度）| NP]]包含了许多人们想要有效解决的问题，但是没有有效的算法，例如[[布尔可满足性问题]、[[哈密顿路径问题]]和[[顶点覆盖问题]]。由于确定性图灵机是一种特殊的非确定性图灵机，因此很容易观察到P中的每个问题也是NP类的成员。 − − The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|url-status=dead|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archivedate=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref> − − 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 <math>O(2^{\sqrt{n \log n}})</math> for graphs with n vertices, although some recent work by Babai offers some potentially new perspectives on this. − − Ladner指出，如果P≠NP，则NP中存在既不是P也不是NP完全的问题。如果图同构是NP完全的，则多项式时间层次会塌缩到第二级。由于人们普遍认为多项式族不会塌缩到任何有限水平，因此图同构不是NP完全的。尽管Babai最近的一些工作提供了一些潜在的新观点，这个问题的最佳算法，属于Lászlóbai和Eugene Luks，他们已经对于有n个顶点的图运行了时间<math>O(2^{\sqrt{n \log n}})</math>。 − − − − ===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. − − '''<font color="#ff8000"> 整数因式分解问题</font>'''是确定给定整数的素数因式分解的计算问题。作为一个'''<font color="#ff8000"> 决策问题</font>'''，它是判断输入是否有一个小于k的素数因子的问题。目前还没有有效的整数分解算法，这一事实构成了几种现代密码系统的基础，如'''<font color="#ff8000"> RSA算法</font>'''。整数分解问题存在于NP和co-NP中（甚至在UP和co-UP中）。如果问题是'''<font color="#ff8000"> NP完全问题</font>'''，多项式时间层次将崩溃到第一级（即NP等于co-NP）。最著名的整数因式分解算法是一般的数域筛，它需要时间<math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math>来分解一个奇数n。但是，这个问题最著名的量子算法'''<font color="#ff8000"> Shor算法</font>'''是在多项式时间内运行的。不幸的是，这一事实并不能说明非量子复杂性类的问题所在。 − − − 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-完全”的问题。[[图同构问题]、[[离散对数问题]]和[[整数因式分解问题]]是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或是“NP-完全”。 − The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in '''P''', '''NP-complete''', or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation+ − + − 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难处理性== <!-- This section is linked from Minimax, Intractability, Intractable --> − − = = 棘手 = = = < ! -- 本节链接于 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. − − 一个问题在理论上可以解决（例如，给定大量但有限的资源，尤其是时间）。但是在实践中，任何解决方案都需要使用太多的资源才能发挥作用。相反，一个在实践中可以解决的问题字面上被称为“一个可以处理的问题” 。术语Infeasible (字面上的意思是“不可能完成”)这个词有时候可以和棘手的互换使用，尽管这有可能在数学优化时被混淆为一个可行的解决方案。 − − | postscript = .| doi-access = free − − }}</ref> If graph isomorphism is NP-complete, the [[polynomial time hierarchy]] collapses to its second level.<ref>{{cite book | last1 = Schöning | first1 = Uwe | authorlink = Uwe Schöning | title = Graph isomorphism is in the low hierarchy | url = | journal = Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science | volume = 1987 | issue = | pages = 114–124 | doi=10.1007/bfb0039599| series = Lecture Notes in Computer Science | year = 1987 | isbn = 978-3-540-17219-2 }}</ref> 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 <math>O(2^{\sqrt{n \log n}})</math> for graphs with ''n'' vertices, although some recent work by Babai offers some potentially new perspectives on this.<ref>{{cite arXiv |last=Babai |first=László |date=2016 |title=Graph Isomorphism in Quasipolynomial Time |eprint=1512.03547 |class=cs.DS }}</ref> − 易处理的问题经常被认为是与具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 '''<font color="#ff8000"> 退出时间难题extime-hard</font>'''。如果 NP 不等于 P，那么 '''<font color="#ff8000"> NP 难问题</font>'''在这个意义上也是棘手的。+ + − + − 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算法]]，确实在多项式时间内运行。不幸的是，这一事实并不能说明非量子复杂性类的问题所在。 − 然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。+ − ===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.+ − 要了解为什么指数时间算法在实践中通常不可用，请考虑一个在暂停之前执行2<sup>n</sup> 操作的程序。对于小的 n，比如100，假设计算机每秒执行10<sup>12</sup> 操作，程序将运行4 × 10<sup>10</sup> 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。然而，在 n 变得相对较大之前，使用1.0001<sup>n</sup>操作的指数时间算法是可行的。+ − 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.+ − 同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n<sup>15</sup> ，那么认为它有效是不合理的，而且除了小的实例之外，它仍然是无用的。事实上，在实践中，即使是 n<sup>3</sup> 或 n<sup>2</sup> 算法对于实际规模的问题也常常是不切实际的。+ + + − 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/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> “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''，并且不知道它们是不同的类还是相等的类。 第1,135行：
第559行： + − It is suspected that '''P''' and '''BPP''' are equal. However, it is currently open if '''BPP''' = '''NEXP'''.+ − − 有人怀疑“P”和“BPP”相等。但是，如果'''BPP'''=''NEXP''，它当前就是开放的。 第1,145行：
第568行： − + − ==Intractability难解性== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] 本节链接自[[Minimax]]、[[难处理性]]、[[棘手]]-->+ − − {{See also|Combinatorial explosion}} 第1,154行：
第575行： − {{wikt|tractable|feasible|intractability|infeasible}}+ − − 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. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。<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> − − 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年对图灵机的定义，这被证明是一个非常健壮和灵活的计算机简化。 − − {{cite book − − |title=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 建议考虑一个”好的”算法是一个运行时间由输入规模的多项式限定的算法。 − − |first=Justin − − |last=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) ，苏联在这一领域的先驱，研究了另一个具体的复杂性度量。正如他所记得的: − |page=[https://books.google.com/books?id=LWCYBgAAQBAJ&pg=PA132&dq=intractable+infeasible 132]+ − − |year=2015 − − |isbn=978-1-44716639-9 − − }}</ref> − 1967年，Manuel-Blum提出了一组公理（现在称为Blum公理），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的加速定理。这一领域在1971年开始蓬勃发展，当时斯蒂芬·库克和列奥尼德·莱文证明了实际相关问题的存在，这些问题是NP完全的。1972年，Richard Karp以其里程碑式的论文《组合问题中的可约性》（reductability In combinational Problems）将这一想法向前推进了一大步。在这篇论文中，他展示了21个不同的组合和图论问题，每一个都因其计算上的困难而声名狼藉，都是NP完全的。+ − + − 可处理问题通常被认为是具有多项式时间解的问题（''P''，''PTIME''）；这被称为[[科巴姆-埃德蒙兹论]]。在这个意义上，已知的棘手问题包括[[EXPTIME]]-困难的问题。如果NP与P不同，那么[[NP-hard]]问题在这个意义上也是难以解决的。+ 第1,203行：
第594行： + − 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中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，[[预伯格算法]]中的决策问题已被证明不在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.+ − 要了解为什么指数时间算法在实际中通常不可用，请考虑一个在停止之前进行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.+ − 类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”<sup>15</sup>，那么认为它有效是不合理的，而且除了在小的实例上，它仍旧是无用的。实际上，在实践中，即使是''n''<sup>3</sup> 或 ''n''<sup>2</sup> 算法对于实际大小的问题也往往是不切实际的。+ + − ==Continuous complexity theory连续复杂性理论== − + − 连续复杂性理论可以指问题的复杂性理论，这些问题涉及通过离散化近似的连续函数，如[[数值分析]]中所研究的那样。数值分析复杂性理论的一种方法是[[基于信息的复杂性]]。 + − 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。<ref>{{cite arxiv|eprint=0907.3117|last1=Babai|first1=László|last2=Campagnolo|first2=Manuel|title=A Survey on Continuous Time Computations|class=cs.CC|year=2009}}</ref>[[控制理论]]可以看作是一种计算形式，微分方程用于连续时间和混合离散连续时间系统的建模。<ref>{{cite journal | title = Computational Techniques for the Verification of Hybrid Systems | id = {{citeseerx|10.1.1.70.4296}} | first1 = Claire J. | last1 = Tomlin | first2 = Ian | last2 = Mitchell | first3 = Alexandre M. | last3 = Bayen | first4 = Meeko | last4 = Oishi | journal = Proceedings of the IEEE | volume = 91 | issue = 7 | pages = 986–1001 | date = July 2003 | doi = 10.1109/jproc.2003.814621 }}</ref>+ − − ==History历史== − − 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. − − 在明确致力于算法问题复杂性的实际研究开始之前，各种研究人员已经奠定了大量的基础。其中最具影响力的是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> − − 系统地研究计算复杂性的开端，要归功于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: + + − {{quote|However, [my] initial interest [in automata theory] was increasingly set aside in favor of computational complexity, an exciting fusion of combinatorial methods, inherited from [[switching theory]], with the conceptual arsenal of the theory of algorithms. These ideas had occurred to me earlier in 1955 when I coined the term "signalizing function", which is nowadays commonly known as "complexity measure".<ref>Boris Trakhtenbrot, "[https://books.google.com/books?id=GFX2qiLuRAMC&pg=PA1&dq=%22From+Logic+to+Theoretical+Computer+Science+%E2%80%93+An+Update%22&hl=en&sa=X&ved=0ahUKEwivkOPkt-TjAhVHRqwKHUNnAekQ6AEIKjAA#v=onepage&q=%22From%20Logic%20to%20Theoretical%20Computer%20Science%20%E2%80%93%20An%20Update%22&f=false From Logic to Theoretical Computer Science – An Update]". In: ''Pillars of Computer Science'', LNCS 4800, Springer 2008.</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>{{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 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=August 2019}}，一些作者声称，对于实践中出现的典型问题，一般渐近结果往往不重要。<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref> − ==Editor's recommendation编辑推荐==+ + − ==See also请参阅==+ − {{Div col|colwidth=25em}}+ + + − * [[Context of computational complexity]]+ − *[[计算复杂性的上下文]]+ − * [[Descriptive complexity theory]]+ − − * [[Game complexity]]+ − − * [[Leaf language]]+ − − * [[Limits of computation]]+ − − * [[List of complexity classes]]+ − − * [[List of computability and complexity topics]]+ − − * [[List of important publications in theoretical computer science]]+ − − * [[List of unsolved problems in computer science]]+ − + − * [[Parameterized complexity]] − − * [[Proof complexity]]+ − − * [[Quantum complexity theory]]+ − − * [[Structural complexity theory]]+ − − * [[Transcomputational problem]]+ − − * [[Computational complexity of mathematical operations]]+ − − − {{Div col end}} − 第1,369行：
第736行： − ==Works on complexity复杂性的研究==+ − − * {{Citation |editor-first=Shyam |editor-last=Wuppuluri |editor2-first=Francisco A. |editor2-last=Doria|title=Unravelling Complexity: The Life and Work of Gregory Chaitin |publisher=World Scientific |year=2020 |isbn=978-981-12-0006-9 |ref=https://www.worldscientific.com/worldscibooks/10.1142/11270|doi=10.1142/11270 }}+ − − 第1,387行：
第751行： − ==References参考文献==+ − − === Citations 引用===+ − − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 第1,407行：
第811行： − ===Textbooks教材===+ − − *{{Citation+ − + − | author2=Ko, Ker-I − − | author2 = Ko，Ker-I − − | last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora − − | title=Theory of Computational Complexity − − 计算复杂性理论 − − | last2=Barak | first2=Boaz − − | publisher=John Wiley & Sons − − 2012年3月24日 | publisher = 约翰威立 − − | title=Computational Complexity: A Modern Approach − − | year=2000 − − 2000年 − − | url = http://www.cs.princeton.edu/theory/complexity/ − − | isbn=978-0-471-34506-0 − − − − − − }} 第1,465行：
第837行： − * {{Citation+ − + − | authorlink=Oded Goldreich − − | authorlink = Oded Goldreich − − | last1=Downey − − | url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html − − Http://www.wisdom.weizmann.ac.il/~oded/cc-book.html − − | first1=Rod − − | title = Computational Complexity: A Conceptual Perspective − − | title = 计算复杂性: 一个概念性的视角 − − | last2=Fellows − − | publisher = Cambridge University Press − − 剑桥大学出版社 − + − + − − 2008年 − − − − }} 第1,545行：
第890行： − * {{citation+ − − }} − 第1,555行：
第897行： − | last = Papadimitriou+ − − | first = Christos+ − − | authorlink = Christos Papadimitriou+ − − | title = Computational Complexity+ − − | edition = 1st+ − − | year = 1994+ − − | publisher = Addison Wesley+ − − * {{Garey-Johnson}}+ − + − | isbn = 978-0-201-53082-7 − − * {{Citation+ − − }} − 第1,651行：
第981行： − * {{Citation+ − − |location=USA − − | location = USA − − | editor1-last=van Leeuwen − − |isbn=978-0-534-95097-2 − − | isbn = 978-0-534-95097-2 − − | editor1-first=Jan − − − − | title-link = 计算理论简介 − − | editor1-link = Jan van Leeuwen − − }} − 第1,685行：
第994行： − * {{citation+ − + − | last = Papadimitriou − − | first = Christos − − | authorlink = Christos Papadimitriou − − | title = Computational Complexity − − | edition = 1st − − | year = 1994 − − | publisher = Addison Wesley − − | isbn = 978-0-201-53082-7 − − }} − − * {{Citation − 第1,721行：
第1,010行： − <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:待整理页面]]+ + + + + + + + + + + + + + + + + + + + + + + + + +
无编辑摘要
此词条暂由水流心不竞初译，翻译字数共，已由Sizuka初次审校。
{{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 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 complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
'''<font color="#ff8000"> 计算复杂性理论Computational complexity theory</font>'''的重点是根据计算问题的资源使用情况对其进行分类，并将这些类相互关联。计算问题是能由计算机解决的任务。计算问题是可以通过机械应用的数学步骤来解决的，例如算法。
'''<font color="#ff8000">计算复杂性理论 Computational complexity theory</font>'''，侧重于根据计算问题的资源使用情况对它们进行分类，并将这些类相互关联。计算问题是由计算机解决的任务。而机械地应用数学步骤，例如算法，可以解决某个计算问题。
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 [[logic gate|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.<ref>{{cite web |title=P vs NP Problem {{!}} Clay Mathematics Institute |url=http://www.claymath.org/millennium-problems/p-vs-np-problem |website=www.claymath.org |language=en}}</ref>
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
无论使用什么算法，如果某个问题的解决需要使用大量的资源，那么这个问题本身就会被当做是一个难题。而该理论通过引入计算的'''<font color="#ff8000">数学模型 mathematical models </font>'''来研究这些难题并量化其计算复杂性，即解决这些难题所需的资源量，如时间和存储量，将这种直觉形式化。还可以使用其他复杂度来衡量，例如通信量(用于通信复杂度)，电路中的门数(用于电路复杂度)，以及处理器的数量(用于'''<font color="#ff8000">并行计算 parallel computing </font>''')。
计算复杂性理论的作用之一是确定计算机能做什么和不能做什么的实际极限。七个千禧年难题之一的 P vs NP问题，就被认为是属于计算复杂性领域。
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.
Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.
Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.
理论计算机科学中，'''<font color="#ff8000">算法分析 Analysis of algorithms</font>'''和 '''<font color="#ff8000">可计算性理论 Computability theory </font>'''是两个密切相关的领域。算法分析和计算复杂性理论分析的主要区别在于，前者专用于分析特定算法解决问题时所需的资源量，而后者则提出了一个关于所有可用于解决同一问题的所有可能算法的更普遍的问题。更准确地说，计算复杂性理论试图对可能或不能使用适当受限资源解决的问题进行分类。反过来，对可用资源施加限制是区别计算复杂性和可计算性理论的关键所在: 后者的理论提出，原则上可以通过算法解决哪些类型问题。
目录
1 Computational problems计算问题
1.1 Problem instances问题实例
1.2 Representing problem instances表示问题实例
1.3 Decision problems as formal languages作为形式语言的决策问题
1.4 Function problems函数问题
1.5 Measuring the size of an instance测量实例的大小
2 Machine models and complexity measures机器模型与复杂度度量
2.1 Turing machine图灵机
2.2 Other machine models其他机型
2.3 Complexity measures复杂度度量
2.4 Best, worst and average case complexity最佳、最差和平均案例的复杂度
2.5 Upper and lower bounds on the complexity of problems问题复杂性的上下界
3 Complexity classes复杂度类
3.1 Defining complexity classes定义复杂度类
3.2 Important complexity classes重要的复杂性类
3.3 Hierarchy theorems层次定理
3.4 Reduction 归约
4 Important open problems重要的开放性问题
4.1 P versus NP problem P vs NP问题
4.2 Problems in NP not known to be in P or NP-complete NP中不知是P或NP完全问题的问题
4.3 Separations between other complexity classes其他复杂度类之间的分离
5 Intractability难解性
6 Continuous complexity theory连续复杂性理论
7 History历史
8 Editor's recommendation编辑推荐
9 See also请参阅
10 Works on complexity复杂度的研究
11 References参考文献
11.1 Citations 引用
11.2 Textbooks教材
Computational problems计算问题
文件:TSP Deutschland 3.png
A traveling salesman tour through 14 German cities.
A traveling salesman tour through 14 German cities.
拇指|直立=1.5 |旅行商游览了德国14个城市。 A traveling salesman tour through 14 German cities.
一个旅行商（也可译为旅行推销员、货郎担）游览了德国14个城市。
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.
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.
一个计算问题可以看作是一个实例的无限集合，以及每个实例的解决方案。 计算问题的输入<font color="#ff8000">字符串 string </font>称为问题实例，不应与问题本身混淆。在计算复杂性理论中，问题是指要解决的抽象问题。相反，该问题的实例则是一个相当具体的表述，可以用作决策问题的输入。例如，考虑素性测试的问题。实例是一个数字(例如，15) ，如果数字是质数，解决方案是“是” ，否则是“否”(在这种情况下，15不是质数，答案是“否”)。换句话说，实例是问题的特定输入，解决方案是与给定输入对应的输出。
To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 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.
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.
为了进一步强调问题与实例之间的区别，不妨考虑以下关于旅行推销员问题的决策版本: 是否有一条最长2000公里的路线穿过德国所有15个最大的城市？这个特殊问题实例的定量答案对于解决该问题的其他实例几乎没有什么用处，比如要求往返米兰的所有地点，但旅行路线总长度不超过10公里。因此，复杂性理论只针对是的计算问题，而不是针对特定的问题实例。
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 (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 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.
在考虑计算问题时，一个问题实例等于是字母表上的字符串。通常，字母表被认为是<font color="#ff8000">二进制 the binary </font>字母表(即集合{0,1}) ，在这里字符串是位字符串。当考虑现实世界中的计算机时，必须对除了位字符串以外的数学对象进行适当的编码。例如，整数可以用二进制表示法表示，图可以通过它们的<font color="#ff8000">邻接矩阵 adjacency matrices</font>直接进行编码，或者用二进制来编码它们的<font color="#ff8000">邻接表 adjacency lists</font>。
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.
[[图：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.
一个决策问题只有两个可能的输出，对任何输入是或否(或者交替1或0)
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.
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. 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.
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]].
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.
函数问题是一个计算问题，其中每个输入都期望有一个单输出（总函数的），但输出比决策问题更复杂，也就是说输出不只是是或否。值得注意的例子包括<font color="#ff8000">旅行商问题 the traveling salesman problem</font>和整数因子分解问题。
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.
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测量实例的大小
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 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?
为了衡量解决一个计算问题的难度，人们可能希望知道最佳算法解决这个问题需要多长时间。但是，运行时间可能通常取决于实例。特别是较大的实例将需要更长的时间来解决。因此，'''<font color="#32CD32">解决一个问题所需的时间（或所需的空间，或任何复杂程度的度量）的计算，可以当作是一个关于实例大小的函数</font>'''。该实例的大小通常被用作是以比特为单位的输入的大小--[[用户:Sizuka|Sizuka]]（[[用户讨论:Sizuka|不太明白This所代指的含义]]）。复杂度理论感兴趣的是算法如何随着输入大小的增加而伸缩。例如，在求一个图是否连通的问题中，一个2n个顶点的图比一个有n个顶点的图要多花多长时间？
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.
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.
如果输入大小为 n，所花费的时间可以表示为 n 的函数。由于同一大小的不同输入所占用的时间可能不同，最坏情况下的时间复杂度 T(n)被定义为大小为 n 的所有输入所占用的最大时间。如果 T(n)是 n 中的多项式，那么该算法称为'''<font color="#ff8000"> 多项式时间Polynomial time</font>'''算法。'''<font color="#ff8000"> 科巴姆Cobham</font>'''的论文认为，如果一个问题采用'''<font color="#ff8000"> 多项式时间算法</font>'''，那么它可以用可行的资源量来解决。
如果输入大小为 n，则所花费的时间可以表示为 n 的函数。由于同一大小的不同输入所占用的时间可能不同，最坏情况下的时间复杂度T(n)被定义为大小为 n 的所有输入所占用的最大时间。如果 T(n)是n中的多项式，那么该算法称为'''<font color="#ff8000">多项式时间 Polynomial time</font>'''算法。科巴姆 Cobham的论文中，认为如果一个问题允许采用多项式时间算法，便可以用可行的资源量来解决该问题。
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
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.
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.
'''<font color="#ff8000"> 图灵机Turing machine</font>'''是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。<font color="#ff8000"> 图灵机</font>并不是一种实用的计算技术，而是一种计算机的通用模型，（适用于）从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个<font color="#ff8000"> 图灵机</font>来解决这个问题。事实上，这正是'''<font color="#ff8000"> 丘奇-图灵论题Church–Turing thesis</font>'''的表述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如'''<font color="#ff8000"> RAM机器、Conway的生命游戏、元胞自动机</font>'''或任何编程语言都可以在<font color="#ff8000"> 图灵机</font>上进行计算。由于<font color="#ff8000"> 图灵机</font>易于数学分析，并且被认为与任何其他计算模型一样强大，因此是<font color="#ff8000"> 复杂性理论</font>中最常用的模型。
'''<font color="#ff8000">图灵机 Turing machine</font>'''是通用计算机的数学模型。它是一种理论上的设备，可以操纵带条上包含的符号。图灵机并不是作为一种实用的计算技术来使用的，而是作为一种计算机的通用模型，适用于从先进的超级计算机到有铅笔和纸的数学家。研究者们相信如果可以通过算法来解决某个问题，那么就存在解决该问题的图灵机。事实上，这正是'''<font color="#ff8000">邱奇-图灵论题 the Church–Turing thesis</font>''的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如 RAM机、Conway的生命游戏、元胞自动机或任何编程语言都可以在图灵机上进行计算。由于图灵机易于进行数学分析，并且被认为与任何其他计算模型一样强大，因此是复杂性理论中最常用的模型。
Many types of Turing machines are used to define complexity classes, such as [[deterministic Turing machine]]s, [[probabilistic Turing machine]]s, [[non-deterministic Turing machine]]s, [[quantum Turing machine]]s, [[symmetric Turing machine]]s and [[alternating Turing machine]]s. 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.
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 algorithm]]s. 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.
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 [[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 multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.
Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.
文献中提出了许多与标准多带图灵机不同的机器模型，例如随机存取机。可能令人惊讶的是，这些模型中的任何一个可以转换成另一个模型而不需要提供任何额外的计算能力。这些模型交替的时间和内存消耗可能会有所不同。所有模型的共同点是，这些机器都是以确定的方式运行的。
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.
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'')).
For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).
For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).
为了精确定义在给定的时间和空间内解决问题的含义，我们使用了诸如确定型图灵机之类的计算模型。确定型图灵机 M 在输入 x 上所需的时间是该机器在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 M 在长度为 n 的每个输入上所需的时间最多为 f (n) ，则称图灵机M 在时间 f (n)内运行。如果存在一个在时间 f (n)内解决问题的图灵机，则决策问题 A 就可以在时间 f (n)内得到解决。由于复杂性理论热衷于依据问题的难度对它们进行分类，因此人们根据一些标准定义了问题集。例如，在确定型图灵机上，在时间 f (n)内可解决的问题的集合就由 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|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.
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.
可以针对空间需求作出类似的定义。虽然，大家所熟知的复杂度资源是时间和空间，但任何'''<font color="#ff8000">复杂度度量 complexity measure</font>'''都可以视为计算资源。复杂度度量通常是由'''<font color="#ff8000">布鲁姆公理 Blum complexity axioms</font>'''定义的。复杂性理论中使用的其他复杂度度量包括通信复杂度、电路复杂性和决策树复杂度。
The complexity of an algorithm is often expressed using big O notation.
The complexity of an algorithm is often expressed using [[big O notation]].
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 符号来表示。
Best, worst and average case complexity最优、最差和平均案例的复杂度
文件:Sorting quicksort anim.gif
Visualization of the quicksort algorithm that has average case performance O(nlogn).
[[文件：排序快速排序动画.gif|thumb |可视化快速排序算法，它具有平均情况性能O(nlogn).]] Visualization of the [[quicksort algorithm that has average case performance O(nlogn).]]
[[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>.]]
[[具有平均大小写性能的快速排序算法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:
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:
最优、最差和平均情况复杂度，指的是测量相同大小的不同输入的时间复杂度（或任何其他复杂度度量）三种不同的方式。由于一些大小为n的输入可能比其他输入要较快解决，因为我们将复杂度定义如下：
Best-case complexity: This is the complexity of solving the problem for the best input of size n.
Best-case complexity: This is the complexity of solving the problem for the best input of size n.
Best-case complexity: This is the complexity of solving the problem for the best input of size n.
最优情况复杂性: 指的是解决大小为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.
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.
平均情况复杂度: 指的是解决处于平均水平上问题的复杂度。仅针对输入上的概率分布来定义此复杂度。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小为 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.
Amortized analysis: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.
'''<font color="#ff8000"> 平摊分析Amortized analysis</font>''': 在算法的整个系列操作中，平摊分析同时考虑了成本较高和成本较低的操作。
'''<font color="#ff8000">平摊分析 Amortized analysis </font>''': 平摊分析在算法的整个操作系列中，同时考虑了成本较高和成本较低的操作。
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.
Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.
最差情况复杂度: 这是解决大小为 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.
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 [[Big O notation|O]](''n''<sup>2</sup>). 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.
For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n<sup>2</sup>). 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.
例如，考虑确定性排序算法'''<font color="#ff8000"> 快速排序Quicksort</font>'''。它解决了对作为输入的整数列表进行排序的问题。最坏的情况是轴总是列表中的最大值或最小值（因此列表永远不会被拆分）。在这种情况下，算法需要时间O(n<sup>2</sup>)。如果我们假设输入列表的所有可能的排列都是相同的，那么排序所花费的平均时间是O(n log n)。最好的情况发生在每次旋转将列表分成两半时，也需要O(n log n)时间。
例如，考虑确定性排序算法'''<font color="#ff8000">快速排序Quicksort</font>'''。这解决了对作为输入的整数列表进行排序的问题。最差的情况是枢轴始终是列表中的最大值或最小值（因此列表永远不会被拆分）。在这种情况下，算法需要时间O(n2)。如果我们假设输入列表的所有可能排列都是同等可能的的，那么排序所需的平均时间是O(n log n)。当每次旋转将列表分成两半时，最优情况发生，这也需要O(n log n)时间。
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).
对计算时间（或类似的资源，比如空间消耗）进行分类，有助于论证最优算法解决给定问题所需的最长时间的上界和下界。除非另有说明，否则通常则将算法的复杂度视为其最差情况的复杂度。分析一个特定的算法属于'''<font color="#ff8000">算法分析Analysis of algorithms</font>'''的范畴。为了给出某个问题的时间复杂度的上界 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) = 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'') = 7''n''<sup>2</sup> + 15''n'' + 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) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2).
上下界通常使用大 O 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于所使用的计算模型的特定细节。例如，如果 T(n) = 7n2 + 15n + 40, 则以大O表示将写为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:
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:
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)).)
The set of decision problems solvable by a deterministic Turing machine within time f(n). (This complexity class is known as DTIME(f(n)).)
时间 f (n)内<font color="#ff8000">确定性图灵机 </font>可解决的<font color="#ff8000">决策问题 </font>集。(这个复杂性类称为 '''<font color="#ff8000"> DTIME (f (n))</font>'''。)
时间 f (n)内确定型图灵机可解决的决策问题集。(这个复杂度类称为 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's thesis|Cobham-Edmonds thesis]] states that "the time complexities in any two reasonable and general models of computation are polynomially related" {{Harv|Goldreich|2008|loc=Chapter 1.2}}. This forms the basis for the complexity class [[P (complexity)|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 (complexity)|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.
But bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.
但是，通过某些具体的函数 f (n)限制上述计算时间，通常会产生依赖于所选择的机器模型的复杂度类。例如，语言{ xx | x 是任意二进制字符串}可以在多带图灵机上以线性时间求解，但在单带图灵机模型中必然需要二次时间。如果我们允许运行时间的多项式变化，Cobham-Edmonds 论文中指出，”任何两个合理的通用计算模型的时间复杂度都是多项式相关的”。这就形成了复杂度类 P 的基础，P 是一组可以由确定型图灵机在多项式时间内解决的决策问题的集合。相应的一组函数问题是 FP。
Important complexity classes重要的复杂度类
文件:Complexity subsets pspace.svg
A representation of the relation among complexity classes
thumb |右|表示复杂度类之间的关系
A representation of the relation among complexity classes
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:
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”
{ | 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”
{ | 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) )
|}
|}
|}
|}
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]].
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.
用 Savitch 定理证明了 PSPACE = NPSPACE 和 EXPSPACE = NEXPSPACE。
用'''<font color="#ff8000">萨维奇定理Savitch's theorem</font>'''证明了PSPACE = NPSPACE 和 EXPSPACE = NEXPSPACE。
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 (complexity)|BPP]], [[ZPP (complexity)|ZPP]] and [[RP (complexity)|RP]], which are defined using [[probabilistic Turing machine]]s; [[AC (complexity)|AC]] and [[NC (complexity)|NC]], which are defined using Boolean circuits; and [[BQP]] and [[QMA]], which are defined using quantum Turing machines. [[Sharp-P|#P]] is an important complexity class of counting problems (not decision problems). Classes like [[IP (complexity)|IP]] and [[AM (complexity)|AM]] are defined using [[Interactive proof system]]s. [[ALL (complexity)|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.
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.
其他重要的使用概率图灵机定义的复杂度类，包括 BPP、 ZPP 和 RP; AC 和 NC，是使用布尔电路定义的; BQP 和 QMA，是使用量子图灵机定义的。# p 是计数问题(不是决策问题)的一个重要的复杂度类。如 IP 和 AM等类是使用交互式证明系统定义的。ALL 是所有决策问题的类。
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.
对于以这种方式定义的复杂度类，迫切需要证明放宽（例如）对计算时间的要求确实会定义更多的问题。尤其是，尽管DTIME (n)包含在 DTIME (n < sup > 2 )中，但是探讨是不是严格包含这个问题会很有意思。对于时间和空间要求，分别用时间和空间层次定理给出了这些问题的答案。之所以称其为层次定理，是因为它们通过约束各自的资源，在定义的类上生成一个适当的层次结构。因此，存在成对的复杂度类，使得其中一个适当地包含在另一个中。通过已经推导出了这种适当的包含集合，我们可以继续进行定量的陈述，说明需要多少额外的时间或空间才能增加可以解决的问题的数量。
More precisely, the time hierarchy theorem states that
More precisely, the [[time hierarchy theorem]] states that
More precisely, the time hierarchy theorem states that
More precisely, the time hierarchy theorem states that
更准确地说，'''<font color="#ff8000"> 时间层谱定理Time hierarchy theorem</font>'''声称
更准确地说，'''<font color="#ff8000">时间层次定理 Time hierarchy theorem</font>'''表明
Undefined control sequence \sdot.
Undefined control sequence \sdot.
大(f (n) big) subsetneq mathsf { DTIME } big (f (n) sdot log ^ {2}(f (n) big) </math > 。
The space hierarchy theorem states that
The [[space hierarchy theorem]] states that
The space hierarchy theorem states that
The space hierarchy theorem states that
'''<font color="#ff8000"> 空间层谱定理Space hierarchy theorem</font>'''指出
'''<font color="#ff8000">空间层次定理 Space hierarchy theorem</font>'''指出
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.
时间和空间层次定理是复杂度类的大多数分离结果的基础。例如，时间层次定理告诉我们P严格包含在EXPTIME中，而空间层次定理告诉我们L严格包含在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 reduction]]s or [[log-space reduction]]s.
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.
许多复杂度类是使用'''<font color="#ff8000">归约 reduction </font>'''的概念来定义的。归约是将一个问题转化为另一个问题。它抓住了一个非正式的概念，即一个问题最多和另一个问题一样困难。例如，如果一个问题 x 可以用 y 的算法来解决，那么 x 并不比 y 困难，我们说 x 可归约为 y。根据归约方法，归约有多种类型，如库克 Cook归约、 卡普 Karp归约和 莱文Levin 简化，以及归约复杂度的界限，如多项式时间归约或对数空间归约。
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.
最常用的归约是'''<font color="#ff8000">多项式时间归约Polynomial-time reduction </font>'''。这意味着还原过程需要'''<font color="#ff8000">多项式时间polynomial time </font>'''。例如，可以将对整数进行平方的问题归约为两个整数相乘的问题。这意味着两个整数相乘的算法可以用来求一个整数的平方。实际上，这可以通过给乘法算法的两个输入提供相同的输入来实现。因此我们看到平方并不比乘法困难，因为平方可以归约为乘法。
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.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.
这就产生了一个对于复杂度类来说很难解决的问题的概念。如果C中的每一个问题都可以归约为X，那么对于一类问题C来说，问题X是困难的。因此，在C中没有问题比X更难，因为X的算法允许我们解决C中的任何问题。疑难问题的概念取决于所用的归约类型。对于大于P的复杂度类，通常使用多项式时间归约。特别要说明的是，对NP来说难解的问题的集合就是NP-hard问题集。
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, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. 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.]]
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重要的开放性问题==
如果问题X在C中并且对于C来说很难，那么X对于C来说是完全的。这意味着X是C中最难的问题（因为许多问题可能同样困难，因此人们会说X是C中最难的问题之一），因此 非确定性多项式时间复杂度类完全问题（NP完全问题）类包含了NP中最困难的问题，从某种意义上说，它们是可能不在P中的最困难的问题。因为P = NP问题尚未被解决，如果能够将已知的NP完全问题Π2归约为另一个问题Π1，则表明Π1没有已知的多项式时间解。这是因为Π1的多项式时间解会产生Π2的多项式时间解。同样，由于所有NP问题都可以归结为集合，找到一个可以在多项式时间内解决的 NP完全问题意味着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.
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包含了许多人们想要有效解决的问题，但是尚无有效算法可知，例如'''<font color="#ff8000">布尔可满足性问题 the Boolean satisfiability problem</font>'''（有时称为命题可满足性问题）、'''<font color="#ff8000">哈密顿路径问题 the Hamiltonian path problem</font>'''和'''<font color="#ff8000">顶点覆盖问题 the vertex cover problem</font>'''。由于确定型图灵机是一种特殊的非确定型图灵机，因此很容易观察到P中的每个问题也是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.
The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.
P 是否等于 NP 的问题是理论计算机科学中最重要的开放性问题之一，因为其解的广泛意义。如果答案是肯定的，那么许多重要的问题就可以得到更有效的解决方案。这些问题包括运筹学中的各种类型的整数规划问题，物流学中的许多问题，生物学中的蛋白质结构预测，以及找到纯数学定理的正式证明的能力。美国 P/NP问题协会是由美国千禧年大奖难题克雷数学研究所提出的一个建议。为了解决这个问题，设有一个100万美元的奖金。
P 是否等于 NP 的问题是理论计算机科学中最重要的开放性问题之一，因为任何一个解决方案都具有广泛意义。如果答案是肯定的，那么许多重要的问题便可能通过更多有效的方案来解决。其中包括运筹学中的各种类型的整数规划问题，物流中的许多问题，生物学中的蛋白质结构预测，以及找到纯数学定理的形式证明的能力。P 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 (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.
The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, 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包含了许多人们想要有效解决的问题，但是尚无有效的算法，例如'''<font color="#ff8000">布尔可满足性问题 the Boolean satisfiability problem </font>'''、'''<font color="#ff8000">哈密顿路径问题 the Hamiltonian path problem </font>'''和'''<font color="#ff8000">顶点覆盖问题 the vertex cover problem </font>'''。由于确定型图灵机是一种特殊的非确定型图灵机，因此很容易观察到P中的每个问题也是NP类的成员。
[[图同构问题]]是确定两个有限[[图（离散数学）|图]]是否为[[图同构|同构]]的计算问题。复杂度理论中一个重要的未解决的问题是图的同构问题是在“P”、“NP-完全”还是NP-中间。答案不得而知，但人们相信这个问题至少不是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完全的问题。如果'''<font color="#ff8000">图同构 graph isomorphism </font>'''是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.
整数因式分解问题是确定给定整数的质因数分解的计算问题。作为一个决策问题，它是判定输入是否有一个小于k的素因子的问题。目前还没有有效的整数分解算法，这一事实构成了几种现代密码系统的基础，如 RSA算法。整数分解问题存在于NP和co-NP中（甚至在UP和co-UP中）。如果问题是 NP完全问题，多项式时间层次将崩溃到第一级（即NP等于co-NP）。整数因式分解的最著名算法是通用数域筛，它需要时间O(e(649√3)(logn)√3(loglogn)2√3)来分解一个奇数n。但是，这个问题最著名的量子算法 Shor算法，确实是在多项式时间内运行的。不幸的是，这一事实并不能说明非量子复杂性类的问题所在。
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.
Ladner指出，如果“P”≠“NP”，则“NP”中存在既不是“P”也不是“NP-完全”的问题。图同构问题、离散对数问题和整数因式分解问题是被认为是NP中间问题的例子。它们是极少数的NP问题中的一部分，不知道是“P”或是“NP-完全”。
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.
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理论。 从这个意义上讲，棘手的问题包括EXPTIME难以解决的问题。 如果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[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.
整数因式分解问题是确定给定整数的素数因式分解的计算问题。作为一个决策问题，它是决定输入是否有一个素数因子小于“k”的问题。目前还没有有效的整数因式分解算法，这一事实构成了几种现代密码系统的基础，例如 RSA算法。整数因式分解问题出现在“NP”和“co-NP”中（甚至在UP和co-UP[13]）。如果问题是“NP-complete”，则多项式时间层次将塌陷到其第一级（即，“NP”将等于“co-NP”）。最著名的整数因式分解算法是一般数域筛，它需要时间[math]O（e^{\left（\sqrt[3]{\frac{64}{9}\right）\sqrt[3]{（\logn）}\sqrt[3]{（\log\logn）^2}）[/math][14]将奇数整数“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.
然而，这种识别是不确切的：具有较大阶数或较大'''<font color="#ff8000">首项系数 leading coefficient </font>'''的多项式时间解会快速增长，这对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入中却可能是可行的，或者在最坏情况下花费较长时间的解决方案在大多数情况下或平均情况下可能花费较短的时间，因此仍然是实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数情况都不是困难的。例如，以证明Presburger算法中的决策问题不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的 NP完全背包问题，而SAT解算器通常能处理NP完全布尔可满足性问题的大量实例。
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.
要了解为什么指数时间算法通常在实践中不可用，请考虑一个在暂停之前执行2n 操作的程序。对于小的n，比如100，假设计算机每秒执行1012 操作，程序将运行4 × 1010 年，这与宇宙年龄的数量级相同。即使使用速度更快的计算机，该程序也只对非常小的实例有用，从这个意义上说，问题的难解性在某种程度上与技术进步无关。但是，在 n 变得相对较大之前，使用1.0001n操作的指数时间算法是可行的。
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'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, 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.
同样，多项式时间算法也不总是实用的。如果它的运行时间是，比如说，n15 ，那么认为它有效是不合理的，而且除了小的实例之外，否则它仍然是无用的。事实上，在实践中，即使是 n3 或 n2 算法对于实际规模的问题也常常是不切实际的。
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.
同样地，也不知道“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.
有人怀疑“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难解性
脚本错误：没有“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.
An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.
算法复杂性分析的一个早期例子是 Gabriel lamé 在1844年对欧几里德算法的运行时间分析。
算法复杂性分析的一个早期例子是 Gabriel lamé 在1844年对欧几里德算法的运行时间分析。
模板:Wikt
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.
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年，''<font color="#32CD32">Manuel-Blum</font>'''提出了一组公理（现在称为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.
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）；这被称为科巴姆-埃德蒙兹论。在这个意义上，已知的棘手问题包括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 solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.
然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此一般情况下还是实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，预伯格算法中的决策问题已被证明不在P中，但在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，已有算法可以在小于二次时间的大范围内解决NP完全背包问题，并且SAT solver通常能处理NP完全布尔可满足性问题的大型实例。
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.
要了解为什么指数时间算法在实际中通常不可用，请考虑一个在停止之前进行2n操作的程序。对于小的“n”，比如100，假设计算机每秒进行1012 操作，程序将运行大约4 × 1010年，与宇宙年龄的数量级相同。即使有一台速度快得多的计算机，该程序也只对非常小的实例有用，从这个意义上说，一个问题的棘手程度在某种程度上与技术进步无关。然而，在“n”变得相对较大之前，需要1.0001n 运算的指数时间算法是可行的。
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.
类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”15，那么认为它是有效的是不合理的，而且除了在小实例上，它仍然是无用的。实际上，在实践中，即使是n3 或 n2 算法对于实际大小的问题往往是不切实际的。
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 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 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]
连续复杂性理论也可以参考复杂性理论中使用的模拟计算，它使用连续的动力系统和微分方程s。[24]控制理论可以看作是一种计算形式，微分方程用于连续时间和混合离散连续时间系统的建模。[25]
History历史
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é对'''<font color="#ff8000">'欧几里德算法 Euclidean algorithm</font>''的运行时间分析。
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.[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]
系统地研究计算复杂性的开端，要归功于1965年Juris Hartmanis和Richard E.Stearns的开创性论文《算法的计算复杂性》，提出了时间复杂度和空间复杂度的定义，并证明了层次定理。
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 */
padding-left: 1.6em;
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]
Editor's recommendation编辑推荐
See also请参阅
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
1 = Arora | first1 = Sanjeev | authorlink1 = Sanjeev Arora
1 = Arora | first1 = Sanjeev | authorlink1 = Sanjeev Arora
Context of computational complexity
计算复杂性的上下文
| last2=Barak | first2=Boaz
| last2=Barak | first2=Boaz
2 = Barak | first2 = Boaz
2 = Barak | first2 = Boaz
Descriptive complexity theory
| title=Computational Complexity: A Modern Approach
| title=Computational Complexity: A Modern Approach
| title = 计算复杂性: 一种现代方法
| title = 计算复杂性: 一种现代方法
Game complexity
| url = http://www.cs.princeton.edu/theory/complexity/
| url = http://www.cs.princeton.edu/theory/complexity/
Http://www.cs.princeton.edu/theory/complexity/
Http://www.cs.princeton.edu/theory/complexity/
Leaf language
| publisher=Cambridge University Press
| publisher=Cambridge University Press
剑桥大学出版社
剑桥大学出版社
Limits of computation
| year=2009
| year=2009
2009年
2009年
List of complexity classes
| isbn=978-0-521-42426-4
| isbn=978-0-521-42426-4
| isbn = 978-0-521-42426-4
| isbn = 978-0-521-42426-4
List of computability and complexity topics
| zbl=1193.68112
| zbl=1193.68112
1193.68112
1193.68112
List of important publications in theoretical computer science
}}
}}
}}
}}
List of unsolved problems in computer science
Parameterized complexity
| last1=Downey
| last1=Downey
1 = Downey
1 = Downey
Proof complexity
| first1=Rod
| first1=Rod
1 = Rod
1 = Rod
Quantum complexity theory
| last2=Fellows
| last2=Fellows
2 = Fellows
2 = Fellows
Structural complexity theory
| first2=Michael
| first2=Michael
2 = Michael
2 = Michael
Transcomputational problem
| authorlink2=Michael Fellows
| authorlink2=Michael Fellows
2 = Michael Fellows
2 = Michael Fellows
Computational complexity of mathematical operations
| title=Parameterized complexity
| title=Parameterized complexity
参数化复杂度
参数化复杂度
| url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
| url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
Https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
Https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
| publisher = Springer-Verlag
| publisher = Springer-Verlag
Works on complexity复杂性的研究
| location=Berlin, New York
| 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
| year=1999
1999年
1999年
9780387948836
9780387948836
References参考文献
| series=Monographs in Computer Science
| series=Monographs in Computer Science
系列 = 计算机科学专著
系列 = 计算机科学专著
Citations 引用
}}
}}
}}
}}
{{Reflist|30em}}
"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.
一个问题在理论上可以解决（例如，给定大量但有限的资源，尤其是时间）。但是在实践中，任何解决方案都需要使用太多的资源才能发挥作用。相反，一个在实践中可以解决的问题字面上被称为“一个可以处理的问题” 。术语Infeasible (字面上的意思是“不可能完成”)这个词有时候可以和棘手的互换使用，尽管这有可能在数学优化时被混淆为一个可行的解决方案。
| 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.
脚本错误：没有“Footnotes”这个模块。
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
| last = Du
| last = Du
Textbooks教材
| first=Ding-Zhu
| 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)
| isbn = 978-0-471-34506-0
| publisher=Cambridge University Press
}}
}}
第一个 = Oded
第一个 = Oded
Downey, Rod; Fellows, Michael (2008
2008年), [http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
| first2=Michael
Http://www.wisdom.weizmann.ac.il/~oded/cc-book.html 计算复杂性: 一个概念性的视角] Check |url= value (help), Cambridge University Press
| year = 2008
剑桥大学出版社 line feed character in |publisher= at position 27 (help); line feed character in |year= at position 5 (help); line feed character in |url= at position 52 (help); Check date values in: |year= (help)
| authorlink2=Michael Fellows
}}
}}
1990年
1990年
Empty citation (help)
}}
}}
| first=Ding-Zhu
| first=Ding-Zhu
| last = Papadimitriou
| last = Papadimitriou
| last = Papadimitriou
| author2=Ko, Ker-I
| author2=Ko, Ker-I
| first = Christos
第一季，克里斯托
第一季，克里斯托
| title=Theory of Computational Complexity
| title=Theory of Computational Complexity
| authorlink = Christos Papadimitriou
作者/链接 = 赫里斯托斯·帕帕季米特里乌
作者/链接 = 赫里斯托斯·帕帕季米特里乌
| publisher=John Wiley & Sons
| publisher=John Wiley & Sons
| title = Computational Complexity
| title = 计算复杂性
| title = 计算复杂性
| year=2000
| year=2000
| edition = 1st
1st
1st
| isbn=978-0-471-34506-0
| isbn=978-0-471-34506-0
| year = 1994
1994年
1994年
}}
}}
| publisher = Addison Wesley
艾迪生 · 韦斯利
艾迪生 · 韦斯利
模板:Garey-Johnson
| isbn = 978-0-201-53082-7
| isbn = 978-0-201-53082-7
| isbn = 978-0-201-53082-7
Empty citation (help)
}}
}}
| 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-link=Introduction to the Theory of Computation
}}
}}
}}
}}
Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7
{{Citation
|last=Sipser
|last=Sipser
类别: 研究的计算领域
类别: 研究的计算领域
This page was moved from wikipedia:en:Computational complexity theory. Its edit history can be viewed at 计算复杂性理论/edithistory 此页摘自维基百科：英语：计算复杂性理论。其编辑历史记录可在[[编辑历史记录]上查看
分类：有脚本错误的页面有参考文献错误的页面CS1 English-language sources (en)CS1: long volume valuePages with citations using unsupported parameters调用重复模板参数的页面Articles with short description含有受损文件链接的页面保护状态与保护标志不符的页面CS1 errors: invisible charactersPages with citations having redundant parametersCS1 errors: datesPages with URL errorsPages with empty citationsPages with citations lacking titles待整理页面
导航菜单
Sizuka讨论参数设置监视列表贡献退出
页面讨论
阅读编辑查看历史监视更多
搜索
搜索集智百科
集智百科
集智主页
集智斑图
集智学园
最近更改
所有页面
帮助
工具
链入页面
相关更改
上传文件
特殊页面
可打印版本
固定链接
页面信息
此页面最后编辑于2020年11月19日 (星期四) 01:13。
此页面已被访问过766次。
除非另有声明，本网站内容采用知识共享署名-非商业性使用-相同方式共享授权。
隐私政策关于集智百科免责声明手机版视图知识共享署名-非商业性使用-相同方式共享Powered by MediaWiki