复杂性类是由求解所需资源的限制、计算模型以及答案的正确性条件共同定义的一组计算问题。常见的资源包括运行时间、工作内存、随机比特、通信量和量子操作。在计算复杂性理论中,复杂性类提供了一个不依赖于具体程序或机器的问题比较框架。常见的例子包括 P 类和 NP 类:前者包含可在确定性多项式时间内求解的判定问题,后者包含所有肯定答案都具有可在多项式时间内验证的证书的判定问题。
复杂性类描述的是问题,而非某个具体的算法。证明一个算法运行缓慢,并不能说明它所求解的问题本身就很困难:另一种算法可能快得多。证明一个问题属于某个复杂性类,就给出了求解该问题所需资源的上界;而下界和分离定理则揭示了特定计算模型能力的局限。
复杂性类之间的关系构成了理论计算机科学中许多研究的脉络。有些关系已经得到证明,例如非确定性多项式空间类与确定性多项式空间类相等;另一些则仍未解决,其中尤以P与NP问题最为突出。这一框架也不限于要求精确回答“是”或“否”的问题,还延伸到计数、搜索、近似、随机计算和量子计算等领域。
形式基础与历史发展
大多数标准复杂度类都是用判定问题定义的,这类问题的答案只有“是”或“否”。每个问题实例都编码为某个字母表上的有限字符串,该字母表通常为 。一个判定问题可等同于由其所有肯定实例组成的形式语言。例如,可满足布尔公式构成的语言,恰好包含那些存在某种赋值使公式为真的公式编码。这种表示方式使图、整数、逻辑公式和程序等不同对象上的问题能够在统一的数学框架内进行比较。
计算模型规定了允许执行的操作及其代价的度量方式。图灵机是传统的参照模型,不过随机存取机和布尔电路也占据核心地位。对于输入字符串 ,其长度 衡量了所编码的信息量。时间界限计算执行的计算步数,空间界限则计算使用的工作存储空间。在亚线性空间模型中,输入通常存放在只读带上,不计入工作空间限额。否则,仅存储输入就会使任何非平凡的对数空间计算都无法实现。
编码方式很重要,因为复杂度是相对于输入长度来度量的,而不是相对于对象的数值大小。整数 用二进制表示约需 位,用一元编码表示则需要 个符号。因此,一个运行时间与 成正比的算法,相对于二进制输入长度而言,可能具有指数级的运行时间。相比之下,显式表示的图所采用的合理编码方式之间,通常只需多项式级开销即可相互转换。这使得多项式时间分类具有稳健性,而更细致的复杂度区分仍会受到计算模型和表示方式的影响。
现代复杂度理论框架形成于20世纪60年代。1965年,尤里斯·哈特马尼斯和理查德·斯特恩斯发表了关于算法计算复杂度的奠基性研究,其中包括时间层级方面的成果。艾伦·科布汉姆和杰克·埃德蒙兹各自独立开展的工作,推动了以多项式时间作为高效计算的数学表述。斯蒂芬·库克于1971年的研究以及列昂尼德·列文独立完成的研究,确立了非确定性多项式时间中具有核心地位的完全性现象。理查德·卡普于1972年提出的归约,将这一理论与广泛的组合问题联系起来。
复杂度类是问题的数学集合,而不是对软件性能的评级。这种分类通常关注任意大的输入以及最坏情况下的行为,不考虑硬件速度、实现质量以及实际问题实例的许多特性。这些抽象使一般性定理成为可能,但也解释了为什么仅凭理论分类无法预测某个具体应用的运行时间。
确定性时间类
对于函数 ,在给定的机器模型约定下,类 包含所有可由确定性机器在 步内判定的语言。最广为人知的确定性时间类是
这个并集允许每个问题各自具有一个固定的多项式指数,但不允许该指数随输入规模增长。从这一形式定义来看,一个需要 步的算法也属于多项式时间算法,尽管它对大多数输入而言都不切实际。
许多基本计算任务都有多项式时间算法。最短路径问题的判定版本询问是否存在一条代价不超过给定上界的路径,它属于 P。素性检验是另一个例子:马宁德拉·阿格拉瓦尔、尼拉杰·卡亚尔和尼廷·萨克塞纳于 2002 年公布的确定性多项式时间算法,在不依赖任何未经证明的数论假设的情况下,确立了素性判定属于 P。这些例子说明,复杂度类关注的是是否存在某种合适的算法,而不是历史上找到这种算法有多困难。
更大的确定性时间类区分了不同的增长尺度。其中两个重要的例子是
因此,E 的指数是线性的,而 EXP 允许指数为任意固定的多项式。这些类不应与“指数时间算法”这一非正式类别混淆,后者的用法有时不那么精确。类似地,准多项式时间通常写作 ,其增长速度介于多项式时间与许多常见的指数时间界之间。
时间层次定理证明,只要时间资源增加得足够多,就能求解更多的问题。该定理的一种标准表述指出,当时间界满足适当的可构造性条件,并且满足
时, 与 之间存在严格分离。证明采用对角化方法:一台机器模拟时间预算较少的候选机器,并设法在选定的输入上给出与它们不同的结果。因此,P 严格包含于 EXP。
这个定理确立了一个真正的层次结构,但并未确定每个自然问题的确切复杂度。它也没有解决涉及不同计算方式的比较问题,例如确定性多项式时间与非确定性多项式时间之间的比较。关键在于区分两件事:增加同一种资源的可用量,以及改变一个计算步骤所允许表示的操作。
非确定性、验证与完全性
非确定性计算可以分出多个可能的后续计算分支。只要至少有一个分支接受输入,整个计算就接受该输入。这是一条数学上的接受规则,并不意味着普通硬件可以不付出任何代价就探索指数多个分支。NP 类由可通过非确定性机器在多项式时间内判定的语言组成。等价地,语言 属于 NP,当且仅当存在一个多项式 和一个多项式时间验证器 ,使得
字符串 称为证书或见证。对于布尔可满足性问题,一个满足赋值就是这样的证书。对于哈密顿回路问题,可以高效地检查给定的顶点排列,判断它是否描述了一条恰好访问每个顶点一次的回路。这里的区别在于寻找见证与检查给定见证。该定义并不意味着每个否实例都有同样简短的证书。
从语言 到语言 的多项式时间多对一归约,是一个可在多项式时间内计算的函数 ,满足
这样的归约表明,经过高效的预处理后,求解 的算法也可以用来求解 。如果 NP 中的每个问题都可归约到某个问题,该问题就是 NP 难的;如果它既是 NP 难的,又属于 NP,那么它就是 NP 完全的。因此,NP完全性同时包含了下界比较和归属某个复杂度类的上界陈述。仅有NP难性并不意味着问题可判定,也不意味着它属于 NP。
库克–列文定理证明了布尔可满足性问题是 NP 完全的。卡普随后通过一系列归约证明,团、顶点覆盖和哈密顿回路等问题也是 NP 完全的。这些结果解释了为何表面上不同的组合问题,在能否于多项式时间内求解这一点上具有相同的地位。如果任意一个 NP 完全问题属于 P,那么 P 就等于 NP。
coNP 类由 NP 中各语言的补语言组成。不可满足性问题是 coNP 完全的:一个公式是否为是实例,恰好取决于它是否不存在满足赋值。NP 是否等于 coNP 仍是一个未解决的问题。更一般地,多项式层级按照固定数量、交替出现的存在量词块与全称量词块,对多项式时间谓词所定义的问题进行分层。其中,第一个存在量词层是 NP,第一个全称量词层是 coNP。如果 P 等于 NP,整个层级就会塌缩为 P;不同层级之间的其他相等关系也会带来重大的结构性后果。
空间复杂度类与交替计算
空间衡量的是计算使用多少工作内存,而非执行多少步。主要的确定性复杂度类包括 L 和 PSPACE,前者由可在对数空间内求解的问题组成,后者由可在多项式空间内求解的问题组成。与之对应的非确定性复杂度类包括 NL 和 NPSPACE。时间与空间的区别在于,工作内存可以反复使用:多项式空间计算可以执行指数多步,同时反复访问并更新一组数量受限的存储单元。
标准的包含关系链为
确定性多项式空间判定机的不同配置至多有指数多个。由于能够停机的确定性计算不可能重复出现同一配置,其运行时间以配置总数为上界。这就解释了最后一个包含关系。目前尚不清楚上述任何一对相邻类之间的包含关系是否为严格包含,不过其他定理表明,这些包含关系不可能全都是相等关系。
沃尔特·萨维奇于 1970 年证明的 萨维奇定理指出,对于满足适当条件的空间界 ,有
该定理采用的递归可达性算法判断一个配置能否在限定步数内到达另一个配置:通过确定性枚举尝试中间配置,再递归检查前后两段路径。递归过程无须存储整条计算路径,因此节省了空间,代价则是运行时间可能很长。该定理的一个重要推论是 。
在对数空间归约下,有向图可达性问题是 NL 完全的。无向图可达性问题属于 L,这一点由奥默·莱因戈尔德在 2005 年首次公布的研究中确立。另一个重要结果是 ,由尼尔·伊默曼和罗伯特·塞莱普切尼于 1987 年各自独立证明。因此,非确定性对数空间类对补运算封闭;相比之下,NP 是否具有相应的性质仍未解决。
交替图灵机具有存在状态和全称状态。如果至少一个后继状态接受,存在状态就接受;如果所有后继状态都接受,全称状态才接受。交替多项式时间类等于 PSPACE,交替多项式空间类等于 EXP。全量化布尔公式的真值判定问题是 PSPACE 完全的,因为一系列存在量化和全称量化的变量取值选择能够自然地表示这种接受结构。这种联系也解释了为什么广义博弈、规划问题和逻辑验证任务经常会涉及空间复杂度类。
随机化复杂度类与去随机化
随机化算法根据随机比特做出选择。它所属的复杂度类不仅取决于资源上限,也取决于允许的错误。BPP 由这样的判定问题组成:存在一个多项式时间随机化算法,对每个输入都能以至少 的概率给出正确答案。常数 是一种惯例:通过独立重复运行并按多数结果作答,可以将错误率降至指数级小,而运行时间仅增加一个多项式因子。
单侧错误定义了 RP 和 coRP。对于 RP,否实例总是被拒绝,而是实例以至少 的概率被接受。对于 coRP,是实例总是被接受,而否实例以至少 的概率被拒绝。ZPP 由能够在期望多项式时间内以零错误求解的问题组成,并满足
期望多项式时间不同于每次运行都有多项式时间上界:零错误算法偶尔可能耗时长得多,只要其期望运行时间仍为多项式即可。
多项式恒等式检验是随机化计算的一个典型例子。给定一个算术电路,该问题要求判断电路所计算的多项式是否恒等于零。在适当的域上,在随机选取的点处对电路求值,可以以高概率检测出非零多项式。由此得到的过程具有单侧错误:恒等于零的多项式求值结果总是零。一般情形下的高效确定性恒等式检验,仍与算术电路领域的重大问题密切相关。
某些包含关系可以直接由定义得出。P 包含于 BPP,而 RP 包含于 NP,因为一个使算法接受的随机比特串可以充当证书。BPP 包含于多项式层级的第二层存在类和第二层全称类。P 是否等于 BPP 仍是一个开放问题。这一问题关心的是随机性是否为多项式时间判定计算带来渐近优势,而不是随机化算法在实践中是否方便或快速。
去随机化研究如何用确定性构造替代随机选择。用于这一目的的伪随机数生成器必须能够骗过某个指定的计算测试族;与仅仅生成统计性质看似合理的数相比,这一要求更强,也更有针对性。难度与随机性之间的关联结果表明,针对显式计算问题的足够强的复杂度下界,可以推出高效伪随机数生成器的存在。拉塞尔·因帕利亚佐和阿维·威格德森的一项著名成果,将 E 中某个问题的指数级电路难度与等式 P = BPP 联系起来。这类结果揭示了一种出人意料的依赖关系:证明某些计算很困难,可以确立另一些计算并不需要随机性。
计数、多数接受与交互式证明
判定类关注是否存在符合要求的解。计数复杂度则研究解的数量。莱斯利·瓦利安特于 1979 年引入了 类。如果一个函数在某个输入上的值等于一台多项式时间非确定性机器在该输入上的接受路径数,那么这个函数就属于 。计算布尔公式的满足赋值数量就是一个基本例子。与 P 或 NP 不同, 是函数类,而不是语言类。
即使判断解是否存在很容易,计数仍可能很困难。二分图中的完美匹配可以在多项式时间内找到,但在标准计数归约下,计算这类匹配的数量是 完全的。对于一个零一矩阵,这一数量等于它的积和式:
这个公式与行列式的公式相似,但没有正负交替的符号。瓦利安特证明了计算零一矩阵的积和式是 完全的。这成为一个重要例子,说明看似相近的代数表达式,其计算问题的已知复杂度却可能大不相同。
PP 是一个基于多数接受的判定类。如果一台多项式时间概率机器接受“是”实例的概率严格大于 ,而接受“否”实例的概率至多为 ,那么该机器所判定的语言就属于 PP。与 BPP 不同,PP 不要求接受概率与 之间存在固定的间隔;其超出 的幅度可以小到指数级。因此,重复运行通常无法将 PP 计算转化为有界错误的多项式时间算法。1991 年证明的户田定理指出,整个多项式层级都包含在 中;在这一计算模型中,多项式时间机器可以向一个 函数预言机发出查询。
交互式证明系统允许计算能力受限的验证者与计算能力不受限制的证明者交换消息。完备性要求:对于真命题,验证者可以通过与合适的证明者交互,以高概率接受。可靠性要求:对于假命题,无论证明者采取何种策略,验证者接受的概率都必须很低。IP 类允许验证者使用多项式时间随机计算,并进行多项式轮通信。
阿迪·沙米尔于 1992 年证明了 。证明使用了算术化方法,将逻辑命题转化为可以通过随机化交互检验的多项式恒等式。这使验证超越了定义 NP 时所使用的单个静态证书。另一方面,概率可检验证明定理通过这样一类验证者刻画了 NP:它们只使用对数数量的随机比特,并且只检查证明中常数个位置。这些结果将复杂度类与证明结构、错误检测及近似求解的难度联系起来。
电路、非一致性与并行计算
布尔电路通过与门、或门、非门等逻辑门计算函数,门之间的连接不形成有向环。电路的规模用门的数量衡量,深度则用从输入到输出的最长依赖链衡量。电路族为每一种输入长度 提供一个电路 。这与普通算法不同:普通算法用同一个有限程序处理所有长度的输入。
复杂度类 由具有多项式规模电路族的语言组成。其定义是非一致的:它不要求存在从 高效构造 的过程。等价地,可以让一台多项式时间机器接收一个多项式长度的建议串,该建议串只取决于输入长度。由于这一系列建议串可以编码任意信息, 包含一些不可判定语言。因此,它并不只是把 P 中的机器换成更快机器后得到的版本。
一致性条件对电路族的生成方式施加限制。例如,对数空间一致性要求有一个对数空间过程能够生成电路的描述。这类限制使电路类与有效算法的对应更加紧密。NC 由可通过一致的、多项式规模且深度为多对数的电路求解的问题组成,这些电路使用扇入有界的门。它将使用多项式数量的处理器、经过少量同步阶段完成的高效并行计算形式化。P 是否等于 NC 仍是一个未解决的问题。
P 完全问题是在足够弱的归约下,P 中最难的问题;这里通常采用对数空间多对一归约。电路值问题要求确定给定布尔电路在指定输入下的输出,它是 P 完全的。如果某个 P 完全问题属于标准的一致 NC,那么 P 就等于 NC。这为实现高度高效的并行化设置了一个条件性障碍,但并不意味着已经有定理证明这类问题无法从并行硬件中获益。
电路复杂度还研究受限的门集合与深度界。复杂度类 允许使用常数深度、多项式规模的电路,其中包含扇入无界的与门、或门以及非门。多项式规模的 电路无法计算奇偶函数,这是 20 世纪 80 年代确立的一项重要下界结果。允许使用阈值门便得到 ,它能够高效计算奇偶函数和许多算术函数。这些分离结果展示了特定运算的能力,也凸显出将下界证明技术推广到不受限制的多项式规模电路有多么困难。
量子复杂度类
量子复杂度类采用基于量子力学的计算模型。标准模型是作用于量子比特的一个一致量子电路族,电路执行后进行测量。BQP 由可通过多项式规模的一致量子电路以有界错误率求解的判定问题组成。与 BPP 一样,错误率可以通过重复运行来降低,因此,具体采用哪个固定的成功概率阈值并不具有根本意义。
量子计算并不是简单地检查所有候选答案,然后揭示正确答案。尽管量子态可以是许多基态的叠加,测量却无法让人不受限制地获取其全部振幅。算法必须巧妙地安排干涉,使有用的结果更有可能出现。1994 年提出的肖尔算法为整数分解和离散对数提供了多项式时间量子算法;这两个问题通常自然地表述为函数问题,也各有相应的判定版本。该算法并未证明 NP 完全问题属于 BQP。
已知的包含关系有
BQP 是否等于 BPP 尚不清楚。BQP 与 NP 的关系也尚未解决:目前既不知道前者是否包含后者,也不知道后者是否包含前者。整数分解无法解决这一比较问题,因为它是否为 NP 完全问题仍然未知。因此,量子优势的证据针对的是特定问题和计算任务,而不是已经证明量子计算普遍具备求解所有可高效验证问题的能力。
QMA 是 NP 式验证的量子对应物。对于答案为“是”的实例,存在一个多项式规模的量子见证,使多项式时间量子验证器以高概率接受;对于答案为“否”的实例,任何见证都只能以低概率被接受。局域哈密顿量问题是一个核心的 QMA 完全问题。在其承诺问题表述中,任务是区分局域量子相互作用之和的最低本征值究竟低于某个阈值,还是高于另一个阈值,并保证两个阈值之间存在间隔。阿列克谢·基塔耶夫证明了该问题的奠基性完全性结果。
承诺问题在量子复杂度中尤为重要。承诺规定了算法必须给出正确结果的输入集合;对于该集合之外的输入,算法的行为不受限制。这一框架能够处理谱隙、近似容差,以及那些无法自然地归为覆盖所有输入的是非判定的区分任务。量子复杂度类的定义还会规定一致性要求和可高效实现的门集。如果没有这些限制,任意实数振幅或非一致的电路选择就可能编码预期计算模型无法有效获取的信息。
搜索、近似与参数化复杂度类
许多计算任务并不只返回一个用于判定的比特。搜索问题可能要求找出一个满足赋值、一个整数的因子,或图中的一条路径。FP 是可在多项式时间内由确定性计算求出的函数所构成的类。FNP 刻画的是这样一类搜索关系:输出长度有多项式上界,且输出的有效性可以在多项式时间内验证。这些函数类和关系类是对判定类的补充,而非替代。
对于某些问题,高效的判定算法能够带来高效的搜索算法。利用可满足性判定算法,可以逐一固定变量,并询问剩余公式是否可满足,从而构造出一个满足赋值。这种性质称为自归约性。它解释了为什么对于许多标准的 NP 问题,判定解是否存在与给出一个见证具有密切相关的复杂度。不过,这种等价性仍须针对具体问题或框架加以证明,不能仅凭“搜索问题”这一名称就得出结论。
优化又引入了另一种区别。精确优化任务要求找出最优的可行解,而近似算法则寻求一个与最优值相差不超过指定倍数的解。对于最小化问题,近似比 通常表示返回解的代价至多为最优值的 倍。APX 包含满足相应条件、且允许多项式时间常数因子近似的 NP 优化问题。多项式时间近似方案对每个固定的 都能给出 近似,但其运行时间对 的依赖可能导致很高的计算开销。全多项式时间近似方案的运行时间则对输入长度和 都是多项式的。
参数化复杂度同时用实例的总规模 和一个指定参数 来衡量实例。如果一个问题能够在如下时间内求解,就称它是固定参数可解的:
其中, 的指数与 无关。这与 之类的时间界不同,后者属于范围更广的 XP 类。以允许的覆盖大小为参数时,顶点覆盖问题是固定参数可解的:针对一条尚未被覆盖的边进行分支,每个分支都会使剩余参数减一,由此得到的基本算法对 呈指数依赖,但对图的规模呈多项式依赖。以团的大小为参数时,团问题是 W[1] 完全的,目前尚不清楚它是否固定参数可解。
这些框架表明,经典的最坏情况分类并不能穷尽计算问题的各种表现。一个 NP 完全问题也可能具有实用的参数化算法、近似保证,或在受限的实例族上存在高效解法。另一方面,关于平均情况的论断必须明确指定输入的概率分布。仅凭最坏情况下的困难性定理,并不能断定随机生成或实践中遇到的实例也是困难的。
结构关系、下界与证明障碍
复杂度理论既研究单个问题,也同样重视各个类之间的关系。包含关系 表示,每个符合 定义的问题也都符合 的定义。严格包含则要求较大的类中存在一个不属于较小类的问题。完全性为整个类提供了代表性问题,但它总是相对于某种指定的归约而言的。多项式时间归约、对数空间归约、随机归约和计数归约可能产生不同的分类结果。
封闭性质提供了结构信息。P 对补集、并集和交集运算封闭。NP 对并集和交集运算封闭,但如果它对补集运算也封闭,就意味着 NP = coNP。PSPACE 对补集运算封闭,因为确定型判定器可以交换其接受与拒绝的结果。即使尚无法直接证明某些类彼此分离,这些事实也能约束它们之间可能存在的关系。条件性坍缩定理尤其富有启发性:卡普–利普顿定理指出,如果 NP 包含于 ,那么多项式层级就会坍缩到第二层。
相对化研究的是配备了预言机的机器;预言机能够在一步内回答某个固定语言的成员资格查询。1975 年,西奥多·贝克、约翰·吉尔和罗伯特·索洛维构造出了一些预言机,使得相对于它们有 P = NP;他们也构造出了另一些预言机,使得相对于它们有 P ≠ NP。因此,如果一种证明技术相对于任何预言机都能原封不动地奏效,它就无法解决 P 与 NP 问题。这是对一大类论证方法的限制,并不意味着这个问题没有确定的数学答案。
其他障碍涉及证明下界的方法。亚历山大·拉兹博罗夫和史蒂文·鲁迪奇于 1997 年提出的自然证明框架表明,在适当的密码学困难性假设下,一大类兼具构造性与充分广泛性的电路性质,无法用于证明所期望的强电路下界。斯科特·阿伦森和阿维·威格德森于 2008 年引入了代数化概念,用以刻画这样一些技术的局限:即使将预言机访问作某些代数扩展,这些技术仍然有效。这些框架的适用范围各不相同,而且没有任何一个框架排除了所有可能的方法。
受限模型与一般模型之间的区别依然至关重要。对于常数深度电路、单调电路以及其他多种受限系统,人们已经证明了很强的下界;而对于不受限电路,证明类似的下界仍然困难得多。同样,时间层级定理将 P 与 EXP 区分开来,却没有指出二者之间的哪些包含关系必然是严格的。因此,关于复杂度类的一项断言包含几个不可或缺的要素:输入表示、计算模型、资源界限、接受条件、一致性要求以及归约概念。改变其中任何一项,都可能同时改变这个类本身以及困难性定理的含义。