独特博弈猜想：NP难解的近似难题
2025-05-10
2002年，Khot提出独特博弈猜想（UGC），认为确定一种名为“独特博弈”的游戏近似值的问题具有NP难的计算复杂度。这一猜想在近似难解性理论中具有广泛应用，如果成立且P≠NP，则许多重要问题不仅无法在多项式时间内得到精确解，也无法得到良好的多项式时间近似解。学术界对UGC的真伪存在争议，其等价表述多种多样，例如标签覆盖问题、Max2Lin(k)问题等，都与计算拓扑相关。近些年，虽然部分更强的形式已被证伪，但对UGC的研究促进了许多有趣的数学研究，并有学者对其进行了部分证明。
开发
NP难