未解决问题，应用与计算数学，2002年提出

唯一博弈猜想

未解决

对任意 $\varepsilon > 0$ ，存在字母表大小 $k = k(\varepsilon)$ ，使得对于给定在大小为 $k$ 的字母表上的唯一标签覆盖实例（其中每对变量 $u, v$ 之间的约束是一个双射 $\pi_{u,v} : [k] \to [k]$ ），区分是否存在满足至少 $1 - \varepsilon$ 比例约束的标签赋值，还是没有任何赋值能满足超过 $\varepsilon$ 比例的约束，是NP困难的。

研究前沿截至2026年

截至2026年，具有 $1$ -对- $1$ 约束的完整唯一博弈猜想仍未解决。2018年科特、明泽与萨夫拉对 $2$ -对- $2$ 博弈猜想的突破性解决，证明了区分可满足比例为 $(1/2 - \varepsilon)$ 与 $\varepsilon$ 的唯一博弈是NP困难的，从而给出了顶点覆盖问题接近 $\sqrt{2}$ 的无条件近似困难性，而将完备性从 $1/2$ 提升至 $1 - \varepsilon$ 仍是核心挑战。

已知最佳结果

$2$ -对- $2$ 博弈定理（科特–明泽–萨夫拉，2018年）证明，对任意 $\varepsilon > 0$ ，区分值至少为 $1/2 - \varepsilon$ 与值至多为 $\varepsilon$ 的唯一博弈实例是NP困难的。
亚指数时间算法（阿罗拉–巴拉克–施トイ勒，2010年）利用谱图划分与拉塞尔/平方和（SoS）层级，可在 $\exp(k \cdot n^{\varepsilon^{O(1)}})$ 时间内求解完备性为 $1 - \varepsilon$ 的唯一博弈。

使用的方法及其局限

方法	取得的结果	局限所在
布尔超立方体上的离散傅里叶分析与“多数函数最稳定”定理	通过独裁者测试，将唯一博弈猜想转化为最大割、Max-2SAT 及一般约束满足问题的紧近似困难性界	仅在假设 UGC 成立的前提下证明条件困难性，而不能直接证明唯一博弈本身的NP困难性
格拉斯曼图扩张与非阿贝尔傅里叶分析	通过放大与缩小结构刻画了格拉斯曼图中的非扩张集，从而证明了 $2$ -对- $2$ 博弈猜想	从 $2$ -对- $2$ 约束归约到 $1$ -对- $1$ 双射约束时在完备性上存在固有的 $2$ 倍损失，因而停留在完备性 $1/2 - \varepsilon$

尚未解决的问题

对于任意 $\varepsilon > 0$ ，完备性为 $1 - \varepsilon$ 的唯一博弈猜想是否成立？抑或存在多项式时间算法能区分 $(1 - \varepsilon)$ 可满足实例与 $\varepsilon$ 可满足实例？

参考文献

Subhash Khot (2002). On the power of unique 2-prover 1-round games · DOI:10.1145/509907.510017
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? · DOI:10.1137/S0097539705447372
Prasad Raghavendra (2008). Optimal algorithms and inapproximability results for every CSP? · DOI:10.1145/1374376.1374414
Subhash Khot, Dor Minzer, Muli Safra (2023). Pseudorandom sets in Grassmann graph have near-perfect expansion · DOI:10.4007/annals.2023.198.1.1