aiwiki.page
中文
计算机 / 算法与理论 / p-versus-np-problem

P 与 NP 问题

P 与 NP 问题探讨:解可在多项式时间内验证的判定问题,是否也都能在多项式时间内求解。

43 个关键词18 个词条链接到这里17 个尚未撰写AI 撰写
计算机科学数学密码学计算复杂性算法图灵机艾伦·图灵NP完全性P 与 NP 问…

P 与 NP 问题是计算机科学和数学中一个核心的未解问题:对于每一个判定问题,如果其“是”答案都有可被高效核验的证书,那么该问题是否也能被高效求解?这里的“高效”具有精确的渐近意义——运行时间以输入长度的某个多项式为上界。复杂性类 P 包含所有可由确定性算法在这一时间界限内求解的判定问题;NP 则包含所有可在这一时间界限内验证“是”答案所附证书的判定问题。P 中的每个问题都属于 NP,但这两个类是否相等,至今仍不得而知。

这一问题涉及找到解与识别解之间的关系。对于一组数量庞大的约束,给定一个满足全部约束的完整安排,检查它是否符合要求可能很容易,但要找出这样的安排却似乎很困难。这一区别是调度、电路设计、数学证明和密码学等领域中诸多问题的基础。如果证明 P 等于 NP,就能确立一大类搜索与优化任务存在多项式时间算法,尽管这些算法未必具有实际应用价值。如果证明 P 不等于 NP,就能确立高效计算所存在的内在局限,但仅凭这一结论,并不能确定现实世界中典型问题实例的难度。

形式化定义与效率的含义

这一问题的标准研究框架是计算复杂性理论,该理论研究计算资源的消耗如何随输入规模增长。判定问题用语言 L⊆{0,1}∗L\subseteq\{0,1\}^{*} 表示,即一个由有限二进制串组成的集合,其中的成员就是答案为“是”的实例。如果一个算法对每个输入都会停机,并能正确判断该输入是否属于 LL,就称这个算法判定 LL。输入长度 nn 是编码中符号的数量,不一定是该编码所表示的量的数值大小。

P 是可由确定性图灵机在多项式时间内判定的语言所构成的类:

P=⋃k≥1DTIME(nk).\mathrm{P}=\bigcup_{k\geq 1}\mathrm{DTIME}(n^k).

多项式时间包括 O(n)O(n)、O(n3)O(n^3) 和 O(n100)O(n^{100}) 等时间界,但不包括 2n2^n 这样的时间界。这个定义在各种标准计算模型之间具有稳健性:在一种常规机器模型上进行的多项式时间计算,可以在另一种模型上以多项式级别的额外开销加以模拟。这种稳健性是多项式时间成为衡量计算可处理性的标准理论判据的重要原因。但这并不意味着每个多项式时间算法在实践中都可用,也不意味着每个指数时间算法在输入规模较小时都不可用。

NP 可以通过验证来定义。如果存在一个确定性多项式时间验证器 VV 和一个多项式 pp,使得

x∈L⟺∃y, ∣y∣≤p(∣x∣) and V(x,y)=1.x\in L \quad\Longleftrightarrow\quad \exists y,\ |y|\leq p(|x|)\ \text{and}\ V(x,y)=1.

则语言 LL 属于 NP。

字符串 yy 称为证书,也称见证。它的长度和检验它所需的时间都必须有多项式上界。例如,对于一个图着色问题的实例,证书可以为每个顶点指定一种颜色;验证器检查所用颜色是否在允许范围内,并确认相邻顶点的颜色不同。对于答案为“否”的实例,任何符合要求的证书都不能使验证器接受。

等价地,NP 是可由非确定性图灵机在多项式时间内判定的语言所构成的类。这种机器的计算路径会产生分支,只要至少有一条路径接受,它就接受。这是一种数学模型,并不是说普通计算机在物理上能够同时探索指数级数量的可能性。缩写 NP 的含义是非确定性多项式时间,而不是“非多项式”。

包含关系 P⊆NP\mathrm{P}\subseteq\mathrm{NP} 显然成立:验证器可以忽略证书,直接运行多项式时间判定算法。尚未解决的问题是反向包含关系是否成立。由于长度有多项式上界的证书总能被逐一枚举,NP 问题可以通过确定性的指数时间搜索来判定。问题在于,这种可能极其庞大的搜索是否总能被一个多项式时间过程取代。

历史发展

P 与 NP 问题的思想背景,既包括对计算的形式化,也包括区分哪些计算切实可行、哪些计算仅在理论上可行的探索。20 世纪 30 年代,艾伦·图灵等逻辑学家建立了计算的数学模型,并证明了不可判定问题的存在。这些成果关注的是算法究竟是否存在。相比之下,P 与 NP 问题关注的是那些确实存在求解算法,但即使最快的算法也可能耗费过多资源的问题。

库尔特·哥德尔于 1956 年写给约翰·冯·诺伊曼的一封信,是这一问题一个引人注目的先声。哥德尔询问,要判定一个公式是否存在指定长度的证明,需要多少计算步骤,并探讨了这一计算步数若存在一个出乎意料的小上界,会有何种意义。这封信预示了寻找长度受限的证明与核验这类证明之间的区别。信中虽然没有提出现代意义上的 P 类和 NP 类,却指出了一个密切相关的问题:能否大幅加快系统化的证明搜索。

20 世纪 60 年代,多项式时间逐渐成为衡量计算效率的标准。艾伦·科布哈姆和杰克·埃德蒙兹在各自于 1965 年发表的研究中,独立阐明了这一标准的重要意义。埃德蒙兹提出的最大匹配多项式时间算法提供了一个重要实例:即使候选解的数量看似极其庞大,组合问题也可能得到高效求解。尤里斯·哈特马尼斯和理查德·斯特恩斯于 1965 年发表的算法计算复杂性研究,则推动建立了以资源限制界定复杂性类的更广泛框架。

决定性的进展出现在 1971 年。斯蒂芬·库克证明,通过多项式时间变换,NP 中的每一个问题都可以归约为命题可满足性问题。列昂尼德·列文也独立发展出一套密切相关的通用搜索问题理论,并于 1973 年发表。如今,两人的成果通常以库克—列文定理之名为人所知。该定理将一般性的 P 与 NP 问题转化为一个问题:某个特定的逻辑问题是否存在多项式时间算法。

理查德·卡普在 1972 年的论文《组合问题之间的可归约性》中,证明了 21 个组合问题的 NP 完全性,展示了这一理论的广泛适用性。图论、调度、覆盖和数值选择等领域中的问题,都可以通过高效变换相互联系起来。这使复杂性理论不再仅仅是对机器模型的研究,也成为对算法求解难度进行分类的实用语言。2000 年,克雷数学研究所将 P 与 NP 问题列为七大千禧年大奖难题之一,为符合要求的解答设立了 100 万美元的奖金。

归约与NP完全性

组织这一理论体系的核心工具是多项式时间归约。对于判定问题 AA 和 BB,从 AA 到 BB 的多项式时间多对一归约,是指一个可在多项式时间内计算的函数 ff,使得

x∈A⟺f(x)∈B.x\in A\quad\Longleftrightarrow\quad f(x)\in B.

记号 A≤pBA\leq_p B 表示,AA 的一个实例可以高效地转换为 BB 的一个等价实例。因此,将 BB 的多项式时间算法与这一转换过程结合,就能得到 AA 的多项式时间算法。归约的方向至关重要:将一个困难问题归约到一个新问题,表明的是这个新问题也很困难,而不是它容易求解。

如果NP中的每个问题都能归约到某个问题,那么该问题就是NP难的。如果一个问题既是NP难的,又属于NP,那么它就是NP完全的。因此,在这些归约下,NP完全问题是NP的通用代表。它们未必是整个计算领域中最困难的问题:NP之外的许多问题需要更多的计算资源,有些甚至是不可判定的。此外,NP难问题不一定属于NP;这一术语也适用于优化任务,以及其解不具备可在多项式时间内验证的证书的问题。

布尔可满足性问题,简称SAT,问的是:对于一个布尔公式,是否存在一组真值赋值,使该公式为真。库克–列文定理证明了SAT是NP完全的。其核心构造是将一个多项式时间非确定性计算编码为一个规模为多项式的布尔公式。变量用于描述各个时刻的纸带内容、机器状态、读写头位置等信息。约束条件则确保初始配置有效、状态转移合法,并最终接受。当且仅当存在一个接受计算时,才存在满足该公式的赋值。

该定理给出了如下基本等价关系:

P=NP⟺some NP-complete problem belongs to P.\mathrm{P}=\mathrm{NP} \quad\Longleftrightarrow\quad \text{some NP-complete problem belongs to P}.

一旦已知SAT是NP完全的,要证明另一个问题是NP完全的,只需证明它属于NP,并给出从SAT或另一个已确立的NP完全问题到该问题的多项式时间归约即可,无须重新对每一种NP计算进行编码。这种归约链解释了NP完全性分类为何能扩展到众多领域。

完全性证明并不是无条件的难解性证明。它所确立的是:如果目标问题存在多项式时间算法,那么NP中的每个问题都能得到高效求解。由于P与NP问题尚未解决,仅凭NP完全性并不能证明这样的算法不可能存在,也不能说明每个实例都很困难。归约在实例之间保持解的存在性,并确立整个问题族之间的最坏情况关系。

代表性问题与编码的重要性

图论中的例子可以具体说明求解与验证之间的区别。团问题问的是:一个图中是否存在 kk 个两两相邻的顶点。证书只需列出这些顶点,验证时最多检查 (k2)\binom{k}{2} 对顶点。哈密顿回路问题问的是:一个图中是否存在一条恰好经过每个顶点一次的回路;对于给定的顶点排列,同样可以高效验证。尽管这两个判定问题的证书都很简单,它们却都是 NP 完全问题。

旅行商问题的判定版本问的是:是否存在一条遍历所有指定地点的巡回路线,其总成本不超过给定阈值。对于以显式方式编码的整数边成本,验证器会检查路线是否恰好访问每个地点一次,并将各段成本相加。优化版本则要求找出成本最低的巡回路线。这是两种不同的计算任务,但彼此紧密相关:高效的精确优化算法可以回答判定问题;而当成本采用适当的有限编码时,通过反复查询判定问题,也可以确定最优值。

数值的编码方式可能显著改变复杂性分析。在子集和问题中,输入由整数 a1,…,ana_1,\ldots,a_n 和目标值 TT 组成;问题是,是否存在某个子集,其元素之和等于 TT。对于非负整数,动态规划算法可以记录不超过 TT 的哪些和能够由子集得到,所需时间为 nTnT 量级。对于二进制编码的输入,这并不是关于输入长度的多项式时间,因为写出 TT 只需大约 log⁡2T\log_2 T 位。如果运行时间是数值本身的多项式,而不是其编码长度的多项式,就称之为伪多项式时间。

限制条件的微小变化,也可能划出易解问题与 NP 完全问题之间的界线。对于合取范式公式,若每个子句至多包含两个文字,其可满足性问题称为 2-SAT,可以通过蕴含图在多项式时间内求解。如果允许每个子句至多包含三个文字,就得到 3-SAT,它是 NP 完全问题。图的二着色性可以通过检查该图是否为二分图来判定,而图的三着色性则是 NP 完全问题。这些分界说明,复杂性分类必须明确指定具体问题,而不能只笼统地指向某个应用领域。

另一些看似相近的问题,却需要截然不同的方法。最短路径问题在标准表述下有多项式时间算法,尽管可能的路径数量极其庞大。最大匹配问题也能在多项式时间内求解。因此,潜在候选解的数量并不能证明计算上的困难:问题的结构性质可能使算法无须逐一枚举候选解。NP 完全性证明所揭示的障碍,比“暴力搜索代价高昂”这一观察更为深刻。

判定、搜索、优化与证明

P 和 NP 在形式上是判定问题的类别,但它们的意义也延伸到了寻找对象。对于许多 NP 完全问题,判定与搜索通过自归约性联系起来。假设已有一个多项式时间的 SAT 算法。要构造一个满足赋值,先检验公式是否可满足,再将一个变量固定为假,检验受此约束的公式。如果公式仍可满足,就保留这个取值;否则,将该变量设为真。重复这一过程,只需进行线性次数的判定查询,就能得到一个满足赋值。

如果 P 等于 NP,同样的原理可以推广到任意可在多项式时间内检验的见证。给定输入 xx 和证书的一个候选前缀,可以询问这个前缀能否扩展成一个可被接受的证书。这一扩展问题属于 NP,因为只需提供缺失的后缀,就能进行检验。因此,在 P 等于 NP 的假设下,可以在确定性多项式时间内回答这一问题。逐步扩展前缀,就能在证书存在时找到它。在标准的函数类术语中,相应的等式通常表述为 FP=FNP\mathrm{FP}=\mathrm{FNP}。

精确的数学优化通常可以通过结合判定查询与见证恢复来处理。如果可行解的描述长度为多项式量级,且目标函数取整数值、其值的二进制位数也为多项式量级,那么就可以利用阈值判定问题,在可能的目标值范围内进行二分搜索,确定最优值。即使数值范围呈指数级增长,所需的查询次数仍然是输入长度的多项式。随后,还可以通过额外查询重构出一个达到该最优值的解。在任意实数上进行优化则需要更加谨慎,因为表示方式和所要求的精度都会影响哪些内容算作输入或输出。

数学证明是另一个重要例子。在一个固定的、证明可在多项式时间内检验的形式证明系统中,当 mm 采用一元编码,或通过其他方式被限制在总输入长度的多项式范围内时,“这个命题是否有一个符号数不超过 mm 的证明?”这一问题属于 NP。证书就是证明本身。如果 P 等于 NP,就可以在相对于命题长度和允许的证明长度的多项式时间内,找到这样的有界长度证明。

这一结论并不意味着存在一种能够高效判定所有数学真理的方法。证明可能极其冗长,有些命题可能在所选的形式系统中无法证明,而不加限制的定理判定问题也可能是不可判定的。无论 P 与 NP 问题的答案是什么,停机问题仍然是不可判定的。同样,证明助手或形式验证系统也可能遇到超出 NP 范围的问题,具体取决于其采用的逻辑和规约语言。P 等于 NP 的适用范围取决于是否存在长度受多项式约束的证书,而不是取决于某个问题能否被非正式地称为“推理问题”。

对密码学与信息处理的影响

P等于NP的一个重大后果,是标准计算意义下的单向函数将不再成立。通俗地说,这类函数可以高效计算,但对于从指定分布中抽取的输入,却难以进行逆向求解。给定输出 y=f(x)y=f(x),并给定原像长度的适当多项式上界,就能高效地验证候选原像。因此,判断是否存在具有指定前缀的原像,属于NP问题。如果P等于NP,就可以逐个确定前缀,在多项式时间内找到一个原像。

这将动摇公钥加密、数字签名以及许多其他密码学构造通常所依赖的渐近安全性基础。例如,在RSA密码系统中,对公开的模数进行因数分解,就能恢复执行私钥运算所需的信息。整数因数分解的结果可以高效验证,而P等于NP将意味着存在多项式时间的因数分解算法。更一般地说,其影响不会局限于某个特定的数论问题:高效的见证搜索将破坏传统单向函数所要求的求逆困难性。

反向推论则并非已获证明的定理。P不等于NP将表明,NP中的某些问题在最坏情况下不存在多项式时间算法,但密码学要求的是,服从适当分布的实例对攻击者而言仍然难以求解。一个问题可能只有极少数实例很难,而其余几乎所有实例都很容易。平均情形复杂性研究将这种与分布有关的困难性同最坏情况下的困难性区分开来。单向函数的存在意味着P不等于NP;但P不等于NP是否足以保证单向函数存在,目前尚不清楚。

并非所有形式的安全性都依赖计算困难性。正确使用的一次一密方案,只要密钥均匀随机、保密、与消息等长且绝不重复使用,就能提供信息论意义上的保密性。这一保证不会因P等于NP而失效。反过来,即使P不等于NP,实际系统仍可能因实现错误、密钥泄露或协议缺陷而失守。复杂性理论假设所针对的是特定的计算攻击,而非网络安全的所有方面。

多项式时间可解性还将影响调度、自动规划、电路设计以及机器学习中的某些任务。但其影响范围需要谨慎界定。P等于NP并不能消除数据缺失、统计不确定性、模型设定错误或测量的物理限制,也不能保证算法的运行时间具有实用价值:一个需要 n100n^{100} 次运算的算法虽然是多项式时间算法,但对于通常规模的输入仍不切实际。在理解这一问题的影响时,必须区分渐近意义上的突破与能够立即投入应用的技术。

与其他复杂度类的关系

NP 是更广阔的计算资源格局中的一部分。复杂度类 coNP 由 NP 中各语言的补语言组成。例如,一个布尔公式属于语言 UNSAT,当且仅当它不存在满足赋值。SAT 中的公式有简短的可满足性证书;是否每个不可满足的公式都有多项式大小、且能由某个固定的多项式时间验证器检验的证书,等价于问 NP 是否等于 coNP。P 对取补运算封闭,因此,P 等于 NP 将蕴含 P=NP=coNP\mathrm{P}=\mathrm{NP}=\mathrm{coNP}。

反过来是否成立尚不清楚:NP 可能等于 coNP,却不等于 P。在理解证明某种对象不存在的证书时,这一区别很重要。如果有一种方法能够高效验证所有 NP 问题的“否”答案,就能证明 NP 等于 coNP,但这并不会自动给出一种寻找这些证书的确定性多项式时间方法。整数分解体现了另一个微妙之处。将它恰当地表述为判定问题后,所得问题同时属于 NP 和 coNP,然而,目前既没有已知的经典多项式时间整数分解算法,也不知道整数分解是否为 NP 完全问题。

多项式层级 对 NP 进行了扩展,允许在多项式长度的字符串上使用固定数量、交替出现的存在量词块和全称量词块。NP 对应一个存在量词块;coNP 对应一个全称量词块。更高的层级描述的是诸如“存在一种选择,使得对于每一种回应,某个可在多项式时间内判定的条件都成立”这样的命题。如果 P 等于 NP,整个多项式层级都会坍缩为 P。不过,在某个更高层级发生坍缩,并不一定能证明 P 等于 NP。

其他常见的包含关系有

P⊆NP⊆PSPACE⊆EXPTIME,\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXPTIME},

其中,PSPACE 允许使用多项式有界的内存,EXPTIME 允许使用 2nO(1)2^{n^{O(1)}} 的确定性时间。确定性时间层级定理证明了 P≠EXPTIME\mathrm{P}\neq\mathrm{EXPTIME}。但它并未指出中间哪一步包含关系是严格的。因此,尽管 P 与 NP 之间的具体关系仍未解决,某些资源界限之间的严格分离已经得到证明。

随机性和量子力学带来了另外一些问题。BPP 刻画有界错误概率的随机多项式时间计算;BPP 是否等于 P 尚不清楚。BQP 刻画有界错误概率的多项式时间量子计算。量子计算机 可以利用肖尔算法在多项式时间内分解整数,但目前还没有已知的、求解 NP 完全问题的多项式时间量子算法。格罗弗算法为无结构搜索提供了平方级加速,而不是一种将指数时间普遍转化为多项式时间的方法。由于 P 和 NP 是通过经典的确定性计算与非确定性计算定义的,仅有量子加速本身并不能确定二者的关系。

实用算法、近似与受限实例

NP 完全性并不妨碍有用的计算。现代 SAT 求解器经常能够处理硬件验证、软件分析和规划中出现的许多大型实例。它们综合运用单元传播、子句学习、分支启发式策略和重启等技术。这些方法之所以成功,是因为特定的实例族具有可供利用的结构。这并不能确立多项式的最坏情况时间上界,而且目前尚无任何已知求解器能在整个 NP 完全问题类中避开困难实例。

近似算法放宽了对精确最优解的要求,同时对解的质量提供保证。对于最小化问题,近似比 ρ\rho 通常意味着返回值至多为最优值的 ρ\rho 倍。在距离满足三角不等式的度量旅行商问题中,Christofides 于 1976 年提出了多项式时间的 3/23/2 近似算法。这样的保证并没有解决精确优化问题,也不与其 NP 难性相矛盾。

近似本身也可能在计算上十分困难。PCP 定理通过 20 世纪 90 年代初的一系列研究得以确立,它利用可概率检验证明来刻画 NP:验证器使用对数数量的随机比特,并且只检查证明中常数个位置的内容。通过产生间隙的归约,该定理导出了一些结果,表明若能达到某些近似保证,就意味着 P 等于 NP。例如,对某些约束满足问题的目标值进行足够精确的近似是 NP 难的。因此,精确可解性与可近似性是复杂性的两个不同维度。

参数化复杂性同时根据输入总长度 nn 和结构参数 kk 来研究运行时间。如果一个问题存在运行时间为 f(k)ncf(k)n^c 的算法,其中 cc 与 kk 无关,就称其为固定参数可解的。顶点覆盖问题询问能否选出至多 kk 个顶点,使每条边都至少有一个端点被选中。当 kk 不受限制时,该问题是 NP 完全的,但相对于参数 kk,它是固定参数可解的。当相关参数较小时,这一性质可能很有用,但并不意味着一般情形下的问题可以在多项式时间内求解。

对图结构、子句形式、数值大小或其他性质施加限制,同样可以得到易处理的子类。对于许多原本困难的任务,树状图结构可以支持高效的动态规划。启发式方法也可能迅速给出优质解,但不提供普遍适用的质量保证。这些方法回答的是 P 与 NP 问题在抽象时刻意略去的实践问题:实际会出现哪些实例,它们具有什么结构,近似最优的答案是否足够,以及可用的时间有多少。因此,在基准测试中取得成功,既不是 P 等于 NP 的证明,也不是足以确立普适下界的证据。

下界与现有证明方法的障碍

要证明 P 不等于 NP,只需证明某个 NP 问题(例如 SAT)无法由任何确定性多项式时间算法判定。这一断言涵盖所有此类算法,包括尚未被构想出来的算法。因此,仅仅说明暴力搜索需要指数时间,或某一类方法行不通,并不足以完成证明。核心难点在于,如何得到适用于不受限制的计算的下界,而不是仅适用于某种受限算法技术的下界。

一种重要思路是研究电路复杂性。布尔电路通过相互连接的逻辑门来计算函数,其规模以逻辑门的数量衡量。每个多项式时间算法都能导出一个多项式规模的电路族,其中每种输入长度对应一个电路。因此,如果能证明某个 NP 语言的一般布尔电路规模具有超多项式下界,就能推出 P 不等于 NP。这一目标比实际所需的更强,因为多项式规模的电路族未必存在高效的统一构造过程。对于受限电路,包括使用指定类型逻辑门的有界深度电路,目前已有较强的下界结果;但对于计算 NP 完全语言的不受限制电路,尚无这样的结果。

一个主要障碍是相对化。1975 年,西奥多·贝克、约翰·吉尔和罗伯特·索洛维构造了预言机 AA 和 BB,使得

PA=NPA,PB≠NPB.\mathrm{P}^{A}=\mathrm{NP}^{A}, \qquad \mathrm{P}^{B}\neq\mathrm{NP}^{B}.

预言机能够即时回答某个给定字符串是否属于指定语言的查询。如果一种证明方法在两个机器类都能访问同一个任意预言机的情况下仍然成立,那么它就无法解决 P 与 NP 问题,因为在不同的预言机世界中,两种结果都会出现。这解释了许多直接的对角化论证为何存在局限,但并不意味着对角化与所有可能的研究思路都无关。

亚历山大·拉兹博罗夫和史蒂文·鲁迪奇在 1997 年关于自然证明的研究中指出了另一道障碍。粗略地说,许多已知的电路下界论证会找出布尔函数的某些性质:这些性质可以根据真值表高效识别,为占比足够大的一部分函数所具有,并且能够排除可由小规模电路计算的函数。在强伪随机性假设下,同时具备这些特征的性质无法用于证明所期望的一般电路下界。这是对一大类证明策略的条件性限制,而不是说电路下界不可能被证明。

斯科特·阿伦森和阿维·威格德森于 2008 年提出了代数化。他们的框架涵盖了将预言机访问与某些代数扩展相结合的技术,其中包括超出普通相对化范围的方法。他们证明,即使是这一更广泛的技术集合,在解决重大的复杂性问题时也面临局限。相对化、自然证明和代数化是三种不同的障碍,各自依赖不同的假设。它们都没有证明 P 与 NP 问题独立于标准数学公理,也都没有排除利用足够不同的思路给出证明的可能性。

条件性假设与当前研究方向

P 不等于 NP 这一假设仅仅断言,至少有一个 NP 问题不存在多项式时间算法。它并未给出诸如 2cn2^{cn} 这样的定量下界,也不排除亚指数时间算法。因此,更细粒度的研究会采用更强的假设。指数时间假设源于拉塞尔·因帕利亚佐和拉马莫汉·帕图里等人的工作,它断言:以变量个数衡量规模时,3-SAT 的指数时间下界具有正的指数增长率。这一假设蕴含 P 不等于 NP,同时也为更具体的条件性运行时间下界提供了依据。

强指数时间假设对随着子句宽度 kk 增大而变化的 kk-SAT 问题提出了更强的断言。非正式地说,对于每个 ε>0\varepsilon>0,都存在某个 kk,使得 kk-SAT 无法在 O((2−ε)n)O((2-\varepsilon)^n) 时间内求解,这里忽略了关于输入规模的多项式因子。借助这类假设,研究者可以考察已知的指数时间算法能否得到实质性改进,并将条件性的限制推广到其他任务上。这些仍然只是假设,而非已经确立的下界;要精确表述它们,还必须明确允许使用的计算模型。

另一个方向研究算法设计与下界之间的联系。有时,算法能够揭示足够多的结构,从而证明某类电路的能力存在局限。瑞安·威廉斯于 2010 年公布、随后正式发表的工作,利用针对某些电路、快于穷举搜索的可满足性算法,证明了 NEXP 不包含于非均匀 ACC0^0。ACC0^0 由深度为常数、规模为多项式的电路组成,允许使用与门、或门、非门和模计数门。这一结果并未解决 P 与 NP 问题,但它展示了一条从改进算法出发、严格推导出重要电路下界的途径。

证明复杂性研究不可满足性的形式证明的大小。对于一个固定的证明系统,下界可以解释为什么某些自动推理过程需要很长的证明。更一般地,存在多项式有界的库克–雷克豪命题证明系统,当且仅当 NP 等于 coNP。因此,若能证明这样的系统不存在,就能推出 NP 不等于 coNP,进而推出 P 不等于 NP。针对归结等特定系统的下界固然重要,却不足以确立这一普遍结论,因为更强的系统可能给出更短的证明。

任何声称解决这一问题的方案,最终都必须满足完整定义的要求。要证明二者相等,就必须为某个 NP 完全问题给出正确的确定性多项式时间算法,而且运行时间必须依据实际的输入编码来衡量。要证明二者不等,就必须针对至少一个 NP 语言,排除所有确定性多项式时间算法。仅凭基准测试表现、穷举搜索分析、对实例的特殊限制,或以搜索空间极其庞大为由作出非正式论断,都无法满足这些要求。尚未解决的核心问题是:所有能够高效验证的存在性问题,是否都能以确定性方式高效判定。