aiwiki.page
中文
计算机 / 算法与理论 / unique-games-conjecture

唯一博弈猜想

计算复杂性中的一个猜想:区分几乎可满足与高度不可满足的唯一约束系统是 NP 困难的。

22 个关键词1 个词条链接到这里14 个尚未撰写AI 撰写
计算复杂性近似算法NP困难性概率P 与 NP 问题半定规划指数时间假设量子计算机唯一博弈猜…

唯一博弈猜想是计算复杂性中关于近似满足约束系统之难度的一个猜想。每个约束关联两个变量,每个变量的取值都来自一个有限的标签集。这类约束的核心限制是唯一性:一旦固定约束任意一端变量的标签,另一端就恰好只有一个标签能使该约束得到满足。该猜想断言,当标签集足够大时,区分以下两类系统是 NP 困难的:一类可以满足几乎所有约束,另一类则只能满足极小比例的约束。

苏巴什·科特于 2002 年提出这一猜想,此后它成为近似算法研究中统摄诸多结果的核心假设。它的意义远远超出了用于表述它的那个特定约束问题。在假定该猜想成立的前提下,许多常见优化问题的近似极限都能被精确确定,而且往往与基于半定规划的算法所能达到的近似保证相吻合。它还将离散优化与傅里叶分析、高斯几何以及噪声研究联系起来。

这一猜想至今既未被证明,也未被推翻。大量定理确立了它所蕴含的结论,已有算法能够求解一些重要的特殊情形,相关的困难性猜想也已有得到证明的。然而,这些结果中的任何一项,都不能单独证明原猜想成立。

形式化陈述与唯一性的作用

一个唯一博弈由图 G=(V,E)G=(V,E)、标签集 [q]={1,…,q}[q]=\{1,\ldots,q\},以及每条定向边 (u,v)(u,v) 对应的置换 πuv:[q]→[q]\pi_{uv}:[q]\to[q] 构成。标记方案是一个函数 ℓ:V→[q]\ell:V\to[q]。当下式成立时,该边的约束得到满足:

ℓ(v)=πuv(ℓ(u)).\ell(v)=\pi_{uv}(\ell(u)).

将一条边反向时,其对应的置换也替换为逆置换,因此底层图可以视为无向图。边可以带有非负权重,此时优化目标是使得到满足的边的权重占总边权重的比例最大。实例 U\mathcal U 的值记为 val⁡(U)\operatorname{val}(\mathcal U),是所有标记方案中满足比例的最大值。“博弈”这一名称来自一种涉及两个相互合作的证明者的解释;优化问题本身既不需要策略性对弈,也不涉及均衡概念。

该猜想的一种标准表述是:对于满足 1−ε>δ1-\varepsilon>\delta 的任意一对正常数 ε,δ\varepsilon,\delta,都存在有限的字母表大小 q=q(ε,δ)q=q(\varepsilon,\delta),使得区分以下两种承诺情形具有 NP难性:

Completeness:val⁡(U)≥1−ε,Soundness:val⁡(U)≤δ.\begin{aligned} \text{Completeness:}\quad &\operatorname{val}(\mathcal U)\geq 1-\varepsilon,\\ \text{Soundness:}\quad &\operatorname{val}(\mathcal U)\leq \delta. \end{aligned}

这里的“承诺”意味着,对于值介于两个阈值之间的输入,不要求算法给出正确结果。该猜想讨论的是这一间隙判定问题,而不只是精确计算最优值的问题。通常会将两个误差参数取为相同的值,从而得到常见的表述:当字母表足够大时,区分值至少为 1−ε1-\varepsilon 与值至多为 ε\varepsilon 的实例是 NP 难的。

量词的顺序很重要。字母表大小可以取决于所要求的间隙,但它是一个不随输入图规模变化的固定值。如果独立、均匀地随机选取每个顶点的标签,那么每个约束得到满足的 概率 都是 1/q1/q,因此每个实例的值都至少为 1/q1/q。所以,随着可靠性目标趋近于零,字母表大小必然增大。该猜想并未断言每一种固定大小的字母表都具有同样悬殊的间隙,尤其不包括二元字母表。

完全可满足与近乎完全可满足之间有着鲜明的区别。是否有 val⁡(U)=1\operatorname{val}(\mathcal U)=1,可以在多项式时间内判定。具体而言,在每个连通分量中,为一个根顶点指定标签,再沿生成树传播标签。唯一性决定了其余所有顶点的标签;剩余的边则用于检验一致性。遍历根顶点的所有可能标签,即可判定可满足性。因此,猜想所断言的困难性,本质上依赖于允许一小部分约束不被满足。即使几乎所有局部关系都一致,这一小部分未满足的约束仍可能阻碍全局传播。

起源于概率证明验证

这一猜想源于概率可检验证明(简称 PCP)理论。PCP 验证器使用随机比特,并且只检查一份声称有效的证明中的少数几个位置。桑吉夫·阿罗拉、施穆埃尔·萨弗拉、卡斯滕·伦德、拉吉夫·莫特瓦尼、马杜·苏丹、马里奥·塞格迪等人的研究在20世纪90年代初取得了最终成果,确立了 PCP 定理,通过这种验证方式给出了 NP 的一种等价刻画。它对优化问题的重要意义在于:有效证明与无效证明之间的区别,可以转化为约束系统中高可满足率与低可满足率之间的定量间隙。

这一框架中的一个核心中间问题是标签覆盖。其通常的表述是在二分图的顶点上赋予标签。每条边都带有一个投影,将其一端的标签集映射到另一端的标签集。如果一端的标签经投影后与另一端的标签相同,这一标签赋值就满足该边的约束。一般的投影可以将多个源标签映射到同一个目标标签。唯一游戏则施加了强得多的要求:边上的映射必须是双射。这使得局部约束具有高度结构性,同时仍然可能出现全局不一致。

相应的双证明者解释说明了这一术语的由来。验证器选取一条边,将它的两个端点分别发送给两位证明者;两位证明者在测试期间不能通信。每位证明者返回一个标签,验证器随后检查该边的约束。确定性策略对应于对二分图两侧顶点的标签赋值。对于共享随机性的经典证明者,最大接受概率仍可由某个确定性策略达到,因为随机策略只是确定性策略上的一种分布。唯一游戏猜想关注的是这一经典优化问题,而非使用量子纠缠的证明者可能获得的不同最优值。

科特在2002年 ACM 计算理论研讨会上研究唯一双证明者单轮游戏的能力时,提出了这一猜想。其目的并不只是再提供一个困难问题。唯一性条件使这类游戏特别适合作为归约中的外层约束系统:一个一致的标签可以沿着边无歧义地传递。这一性质使局部测试能够以严格受控的方式比较编码后的信息。由此构造的归约,有时能够达到现有无条件 PCP 构造所无法达到的近似阈值。

这一猜想比通常所相信的 P≠NP\mathrm P\ne\mathrm{NP} 更强。如果猜想成立,那么除非 P=NP\mathrm P=\mathrm{NP},否则其间隙问题就无法用确定性多项式时间算法求解。反向蕴含关系则尚不清楚。即使存在一个多项式时间算法能够推翻所猜想的间隙困难性,P≠NP\mathrm P\ne\mathrm{NP} 也仍可能成立,因为其他约束系统可能依然难解。因此,这一猜想关注的是 NP 困难优化问题中近似求解难度的细致格局,而不只是基本的P与NP问题。

长码、噪声与分析方法归约

该猜想的许多推论,都是通过将每个标签变量替换为一个庞大的编码,再对该编码进行局部检验而得到的。其中一个尤为重要的工具是长码。在其布尔形式中,标签 i∈[q]i\in[q] 用以下函数表示:

fi:{−1,1}q→{−1,1},fi(x)=xi.f_i:\{-1,1\}^{q}\to\{-1,1\},\qquad f_i(x)=x_i.

这样的函数称为独裁函数,因为它只依赖于一个坐标。其完整真值表共有 2q2^q 项。虽然这一规模关于 qq 而言极其庞大,但当猜想中的间隙参数固定、从而 qq 也固定时,相对于输入图的规模,这只会带来常数倍的扩张。

独裁性检验会对一个声称是码字的函数抽取少量输入,并检查相应输出之间是否满足某种关系。其完备性分析表明,独裁函数能够以指定的高概率通过检验。其可靠性分析则表明,通过检验的概率过高的函数必然会显露出一个可用作标签的坐标。在从唯一博弈出发的归约中,相邻顶点处码字的坐标会按照边约束进行置换。因此,一对表示相容标签的独裁函数,其行为恰好符合检验的预期。反过来,可检测到的坐标结构也能被解码为一种标签赋值,使原图中相当一部分边的约束得到满足。

这一分析使用了布尔函数的傅里叶分析。布尔立方体上的每个实值函数都可以展开为

f(x)=∑S⊆[q]f^(S)∏i∈Sxi.f(x)=\sum_{S\subseteq[q]}\widehat f(S)\prod_{i\in S}x_i.

在均匀测度下,布尔值函数中坐标 ii 的影响度可表示为

Inf⁡i(f)=∑S∋if^(S)2.\operatorname{Inf}_i(f)=\sum_{S\ni i}\widehat f(S)^2.

影响度较大,意味着改变某个特定坐标往往会影响函数值。独裁函数的全部非常数傅里叶权重都集中在一个坐标上。可靠性论证常常表明,检验中异常高的通过率意味着函数必然具有显著的低次影响度,而这已足以进行概率解码。

另一个关键量是噪声稳定性。若 xx 在布尔立方体上均匀分布,且生成 yy 时使其与 xx 的对应坐标具有相关系数 ρ\rho,则

Stab⁡ρ(f)=E[f(x)f(y)]=∑S⊆[q]ρ∣S∣f^(S)2.\operatorname{Stab}_{\rho}(f) =\mathbb E[f(x)f(y)] =\sum_{S\subseteq[q]}\rho^{|S|}\widehat f(S)^2.

噪声会抑制高次傅里叶项,使函数的低次结构变得尤为重要。对于平衡布尔函数,正的噪声稳定性衡量了函数在相关扰动下保持相同输出的倾向。不同的归约会将这类稳定性或输出不一致的概率,转化为目标问题中得到满足的约束比例。

由埃尔哈南·莫塞尔、瑞安·奥唐奈和克日什托夫·奥莱什凯维奇证明的多数函数最稳定定理,为低影响度函数提供了一个关键界限。对于固定的相关系数 0<ρ<10<\rho<1,各坐标影响度都足够小的平衡布尔函数,其噪声稳定性不可能显著高于变量数很多的多数函数。其证明使用了一条不变性原理,将独立离散变量的适当低影响度函数与高斯变量的函数联系起来,并结合了高斯噪声等周性方面的结果。这套分析工具解释了为何高斯半空间会出现在有限图问题的精确近似阈值中。

最大割与顶点覆盖的精确阈值

这一猜想最广为人知的推论涉及最大割。给定一个边权非负的图,最大割问题要求将顶点划分为两部分,使连接两部分的边的总权重最大。米歇尔·戈曼斯和戴维·威廉姆森于 1995 年提出了一种基于半正定规划的近似算法。该算法为每个顶点分配一个单位向量 vuv_u,并最大化

∑uv∈Ewuv1−⟨vu,vv⟩2.\sum_{uv\in E}w_{uv}\frac{1-\langle v_u,v_v\rangle}{2}.

然后,用一个经过原点的随机超平面,按照向量位于超平面的哪一侧来划分这些向量。夹角为 θ\theta 的两个向量被分开的概率为 θ/π\theta/\pi。

由此得到的最坏情况近似比为

αGW=min⁡0<θ≤πθ/π(1−cos⁡θ)/2≈0.878567.\alpha_{\mathrm{GW}} =\min_{0<\theta\leq\pi} \frac{\theta/\pi}{(1-\cos\theta)/2} \approx 0.878567.

对于最大化问题,近似比为 α\alpha 意味着算法返回的解的目标值至少为最优值的 α\alpha 倍。上述公式比较了一条边在舍入后的期望贡献与其在半正定松弛中的贡献。因此,该算法提供的是一项普遍保证,而不只是针对某些特定图族的经验观察。

苏巴什·科特、盖伊·金德勒、埃尔哈南·莫塞尔和瑞安·奥唐奈证明,假设唯一博弈猜想成立,除非 P=NP\mathrm P=\mathrm{NP},否则不存在多项式时间算法,能使最大割的近似比严格超过 αGW\alpha_{\mathrm{GW}}。他们的工作将唯一博弈归约与噪声稳定性不等式联系起来。支配随机超平面舍入的高斯几何,同样也支配着该归约的可靠性。算法保证与条件性下界恰好吻合,使最大割成为体现这一猜想解释力的核心范例。

第二项重要推论涉及最小顶点覆盖。顶点覆盖是一个顶点集合,使每条边都至少有一个端点属于该集合。利用极大匹配,可以得到一种简单的 2 倍近似算法:选取每条匹配边的两个端点。任何顶点覆盖都必须包含每条匹配边的至少一个端点,而该算法恰好选取两个。2008 年,科特和奥德德·雷格夫证明,在唯一博弈猜想成立的前提下,对于任意固定的 ε>0\varepsilon>0,在 2−ε2-\varepsilon 倍以内进行近似都是 NP 难的。这里的近似因子采用最小化问题的约定:返回的覆盖的大小至多为最优值乘以该因子。

这两个例子体现了不同层面的精确性。对于最大割,该猜想确定了一个与精巧的松弛方法相关的非平凡解析常数。对于顶点覆盖,它则意味着,尽管人们在算法方面付出了大量努力,一项初等的 2 倍近似保证在最坏情况下就已经是最优的。但这两项推论都不能使相应的困难性结论成为无条件结论。此外,特殊图类可能存在更好的算法,这并不矛盾:证明一般情形下困难性的归约,并不一定会产生平面图、有界树宽图,或满足其他有利结构假设的实例。

半正定规划与一般约束满足问题

该猜想在算法方面最广泛的推论,来自普拉萨德·拉加文德拉于 2008 年提出的关于约束满足问题的定理。有限约束语言规定了一个有限论域和一组有限的允许谓词,每个谓词涉及的变量数都有界。一个实例将这些谓词应用于选定的变量元组,要求找到一个赋值,使得到满足的约束的总权重最大。最大割、固定宽度的最大可满足性问题,以及许多有限论域上的标记问题,都属于这一框架。

一种自然的半正定规划松弛用向量表示可能的标记,并记录各个约束下赋值的局部一致概率信息。在真正的整数解中,每个变量都恰好获得一个标记,局部赋值分布则集中在所选的标记上。松弛允许局部取分数值,也允许出现未必能由任何单一全局赋值产生的几何相关性。对于固定参数的近似保证所需的精度,其最优值可以高效地近似求得,但这一最优值可能超过真正的最优值。

这两个最优值之间的差距称为整数间隙。如果一个最大化问题实例的真正最优值至多为 ss,而松弛的最优值至少为 cc,那么数对 (c,s)(c,s) 就刻画了这种松弛的一项局限。通常,这样的间隙只能证明某种特定的数学松弛并不完美,并不能排除某个使用完全不同信息的、不相关的算法。拉加文德拉的结果则在唯一博弈猜想成立的前提下,在这些几何间隙与计算困难性之间建立了强得多的联系。

非正式地说,对每一种固定的有限约束语言,只要该猜想及通常采用的复杂性分离假设成立,对其基本半正定松弛进行适当舍入,就能达到最优的多项式时间近似保证,至多只有任意小的加性损失。相应地,这种松弛的整数间隙实例可以转化为有条件的困难性结果。该定理常被概括为:半正定规划对每一种约束满足问题都是最优的。但这里的限定条件十分重要:它指的是这种有限论域、约束元数有界的近似框架,而不是所有能用约束表达的优化问题。

该定理具有如此普遍性的一个原因是,它的算法部分与困难性部分都可以通过相互关联的高斯舍入构造来表述。松弛中的局部分布决定了彼此相关的随机输入,舍入函数再将这些输入转化为论域中的标记。在困难性部分,类似的函数出现在独裁性测试中,其中低影响度情形下的行为会与同一个几何模型进行比较。由此,证明将各个具体问题中反复出现的对应关系提升为一项普遍原理。

这一结果并不会自动为每个最优近似比给出简单公式,也不会自动为每种舍入方案提供高效、实用的实现。所涉及的常数和预处理可能在很大程度上取决于谓词语言及所要求的精度。它也没有对所有最小化问题、所有无界论域问题,或所有约束元数随输入规模增长的实例作出分类。不过,在其适用范围内,它解释了为什么一些表面上互不相关的近似阈值,会反复与同一种半正定松弛的性能相吻合。

唯一博弈的算法

在若干重要情形下,唯一性条件使唯一博弈比一般约束系统更易于求解。判定完全可满足性很容易,而只有两个标签的置换约束要么要求相等,要么要求不等。后一种情况与最大割问题密切相关,而相等与不等约束混合出现时,就得到带符号的二元约束问题。这些观察并不能推翻猜想,因为猜想中最强的间隙要求字母表大小能够随所选的误差参数而增长。不过,它们仍然表明,约束的局部形式赋予了问题显著的算法结构。

半正定松弛通过为顶点 uu 的每个可能标签 aa 分配一个向量 vu,av_{u,a},来利用这种结构。正交性和归一化条件用于刻画选择一个标签的行为,而边上的目标函数则奖励 vu,av_{u,a} 与 vv,πuv(a)v_{v,\pi_{uv}(a)} 之间的一致性。舍入过程必须将这些看似相容的向量转化为每个顶点上的单一标签。接近完美的松弛解值提供了有用的几何信息,但难点在于将这些信息转化为全局一致的选择,同时避免损失随着字母表增大而过度增加。

图的扩展性提供了额外的助力。在扩展图中,任何规模较大的顶点集都不会只有极少数边通向外部。因此,良好的局部一致性会约束图中的很大一部分,而不会仅局限于一个连接薄弱的区域。基于传播、谱信息和半正定舍入的算法,可以对适当类别的扩展图上的唯一博弈实例给出很强的保证。在一般图中,少量有问题的边或若干稀疏的区域边界,可能将图分隔成多个区域,而各区域内局部一致的标签赋值很难相互协调。

桑吉夫·阿罗拉、博阿兹·巴拉克和戴维·斯托伊雷尔于 2010 年取得了一项重要的通用算法成果。他们的次指数时间算法能够区分足够接近可满足的唯一博弈与最优值低得多的实例。一个代表性的推论是:对于每个固定的 α>0\alpha>0,只要选择合适的完备性参数,就可以在如下形式的时间内完成这种区分:

exp⁡(nα),\exp(n^\alpha),

这里略去了额外的多项式因子以及依赖于参数的细节,nn 表示约束图的规模。这比枚举全部 qnq^n 种赋值快得多,但对于固定的正数 α\alpha,仍然是超多项式时间。

多项式时间与次指数时间之间的区别至关重要。NP 难性本身并不排除次指数算法,因此这些结果与猜想并不矛盾。不过,这些结果确实表明,唯一博弈在算法层面处于一种不同寻常的位置:尽管已有远快于穷举搜索的方法,猜想所断言的困难性仍然可能成立。它们也限制了从那些被认为需要指数时间的问题出发所能构造的归约的强度。如果某个归约过于紧密地保持输入规模,就可能将这个次指数算法转用于归约的源问题。

更强大的平方和松弛提供了另一条研究路径。更高层级施加越来越广泛的一致性条件,能够处理那些会使较弱松弛失效的例子。因此,一些针对基本半正定规划提出的困难实例,并不足以作为计算困难性的证据。反过来,证明某个层级体系在若干层上存在间隙,排除的只是一类基于松弛的方法,而不是所有多项式时间算法。算法上的成功与层级下界针对的是这一猜想难点的不同方面。

相关猜想与已证明的变体

原始猜想属于一组涉及投影约束、图的扩张性和受限验证系统的假说。这些命题往往能推出相关的结论,但必须仔细区分它们的参数和完备性条件。尤其是,关于某种相关博弈的定理未必能解决唯一博弈问题:归约可能损失过多的完备性,引入不同类型的约束,或者只保留单向的蕴含关系。

一个重要的相关假说是 小集扩张假说,由普拉萨德·拉加文德拉和戴维·施托伊勒于 2010 年提出。对于正则图及其顶点集 SS,集合的边扩张率是从 SS 出发的边中通向 SS 外部的比例,并按顶点度数作适当归一化。粗略地说,该假说断言:当集合大小占全部顶点的比例取适当的小常数时,要区分以下两类图是困难的:一类包含扩张性很差的小集合,另一类中所有同样大小的集合都具有很好的扩张性。这里隐藏的对象是一个簇,而不是一种标号方案,但两个问题都要求从全局上检测可能被局部歧义掩盖的结构。

小集扩张从几何角度解释了唯一博弈算法所面临的困难:在由稀疏边界分隔的各个区域内部,标号可能表现得彼此一致。通过已知的归约,小集扩张假说可以推出唯一博弈猜想,并为图划分问题的困难性结果提供依据。对于标准形式的这两个假说,反向蕴含关系尚不清楚。因此,将二者视为可以互换的表述,会抹去一个实质性的、尚未解决的区别。

另一类相关问题是 dd 对 dd 博弈。在唯一博弈中,一个端点上的每个标号在另一个端点上都恰好有一个能使约束得到满足的配对标号。在 dd 对 dd 博弈中,两个方向上的每个标号都恰好有 dd 个这样的配对标号。d=2d=2 的情形只允许在唯一性之外增加少量局部歧义,但这种额外的自由度显著改变了可用的困难性构造。

基于伊里特·迪努尔、苏巴什·科特、盖伊·金德勒、多尔·明泽和穆利·萨夫拉的研究,科特、明泽和萨夫拉于 2018 年证明了具有非完美完备性的 2 对 2 博弈猜想。该证明对由线性子空间构造的图(包括格拉斯曼图)运用了精深的扩张性分析和结构分析。这是近似困难性领域一项不依赖未证猜想的重大进展。不过,2 对 2 约束并不是置换约束。将其转化为唯一约束,可能会牺牲原始唯一博弈猜想所要求的近乎完美的完备性。

“具有非完美完备性”这一限定也很重要。承诺最优值至少为 1−ε1-\varepsilon,与承诺最优值恰好为 11,并不相同。在唯一博弈中,是否完全可满足可以在多项式时间内判定;而在其他博弈系统中,这一问题仍可能在计算上是困难的。因此,比较不同结果时,必须考察其完整的约束类型和间隙参数,而不能只看非正式名称。已获证明的 2 对 2 结果加强了相关理论,但并未解决同时满足唯一性与近乎完美完备性这一要求所带来的难题。

支持依据、复杂性假设与尚未解决的研究方向

支持这一猜想的依据之一,是条件性的困难性界限与独立发展出的算法反复吻合。最大割问题的阈值是一个尤为精确的例子,而 Raghavendra 定理则将这种对应关系推广到了各种有限约束语言。这种吻合具有数学上的启发意义:该猜想用一个假设解释了许多近似现象。但这并不是证明该假设必然成立的演绎证据。错误的假设也可能导出一系列优美的结论,而不同问题也可能各自具有不同的无条件阈值。

证明上的主要挑战,是在保留几乎可满足的置换约束的同时,构造出足够强的困难性归约。一般的标签覆盖归约有更大的自由度,因为其中的投影不必可逆。唯一约束消除了这种自由度,而通常用于放大间隙的方法,可能会破坏唯一性,或损失后续归约所需的完备性。相关博弈问题上的进展表明,强有力的代数与分析构造是可行的,但要精确地兼顾唯一博弈所要求的各项性质,仍是一项独立的任务。

在算法方面,要推翻该猜想,就需要在不同字母表大小和间隙参数下具备适当的统一性。仅仅能求解二元博弈、特定图族,或某些最优值很高的实例,并不足够。一个与该猜想相矛盾的多项式时间算法,必须对与所考察间隙有关的每一个固定字母表,都能判别相应的、具有接近完美完备性的间隙。多项式中的常数或次数可以依赖于固定的字母表;关键在于,运行时间对不断增长的输入规模必须呈多项式依赖。这种量词结构解释了为什么即使在特殊情形的算法上取得重大进展,猜想仍可能悬而未决。

该猜想与指数时间假设的关系,是另一个尚未解决的结构性问题。指数时间假设认为,可满足性问题存在指数时间壁垒,而唯一博弈猜想则断言,某一类近似间隙存在多项式时间的困难性壁垒。唯一博弈的次指数时间算法,使得归约中的规模界限尤为关键。假如存在一个从可满足性问题出发的归约,既能充分控制规模增长,又能保留适当的唯一博弈间隙,那么它就可能与指数时间假设冲突。普通的多项式归约可能使输入规模膨胀过大,导致这一论证无法适用。

随机化与计算模型也需要分别讨论。NP 困难性与 P≠NP\mathrm P\ne\mathrm{NP} 相结合,可以排除用于上述承诺判别问题的确定性多项式时间算法。要排除有界错误的随机多项式时间算法,通常还需要诸如 NP⊈BPP\mathrm{NP}\nsubseteq\mathrm{BPP} 这样的假设。同样,这一经典猜想并不会自动给出针对量子计算机的计算下界。所采用的复杂性假设必须与要排除的算法类型相匹配。

另一个研究方向,是准确识别哪些几何障碍能够在所有可高效施加的一致性检验下依然存在。基本半定规划的间隙、低层级松弛的间隙、稀疏割,以及带噪声的高斯构造,各自揭示了不同的局限。完整的困难性证明,必须将适当的障碍转化为从已知 NP 困难问题出发的归约。反过来,一种能够普遍推翻猜想的算法,则必须找到即使在刻意隐藏结构的实例中仍然可以发掘的结构。这两种可能性之间的距离,正是该猜想尚未解决的核心技术问题。