唯一游戏猜想（Unique Games Conjecture）

唯一游戏猜想简称UGC,由苏博特·科特于二零零二年提出。它断言对于一类被称为唯一游戏的约束满足问题,即使几乎所有约束都能满足,要在多项式时间内找到满足即便一小部分约束的赋值也是NP难的,这是一个关于不可近似性的猜想。

概述

唯一游戏是一种特殊的两变量约束满足问题,每条约束是变量间的一一映射,即一旦确定一个变量的取值,另一变量的合法取值就唯一确定。UGC刻画了在几乎可满足与几乎不可满足这两种极端情形之间做区分的困难性。

核心特点

• 约束具有唯一性:给定一端取值,另一端合法取值唯一。
• 猜想断言区分近乎全部可满足与仅极少可满足是NP难的。
• 它比P不等于NP更强,目前尚未被证明也未被否证。
• 若UGC成立,许多问题的半正定规划近似算法被证明是最优的,不存在更好的多项式近似。

应用场景

UGC是近似算法理论的枢纽。在它成立的假设下,可以证明最大割问题、顶点覆盖问题以及一大类约束满足问题的已知近似比恰好是最优的,任何改进都将导致NP难问题被高效求解。这把众多分散的不可近似性结果统一在一个猜想之下,极大地简化了对优化问题近似难度的理解。

常见问题

问:唯一游戏猜想被证明了吗?答:尚未。它仍是开放问题,近年出现的二对二游戏定理被视为对它的重要支持性进展,但完整的猜想至今既未被证明也未被推翻。

问:为什么它被称为统一的不可近似性来源?答:因为在UGC成立的前提下,大量看似不相关的优化问题都能推出精确匹配的近似下界,这些下界往往与半正定规划给出的上界完全吻合,从而统一解释了它们的近似极限。