一意ゲーム予想：計算複雑性理論における驚くべき論争問題

2002年にSubhash Khotによって提案された一意ゲーム予想（UGC）は、一意ゲームと呼ばれる特定の種類のゲームの値を近似することがNP困難であると主張しています。この予想は近似アルゴリズム理論に大きな影響を与えます。もし正しくてP≠NPならば、多くの重要な問題は、正確な解だけでなく、良好な多項式時間近似解も許容しないでしょう。学術界ではその妥当性について意見が分かれており、ラベル被覆問題やMax2Lin(k)問題など、同等の定式化が存在します。より強いバージョンは反証されていますが、UGCの探求は膨大な数学的研究を促し、2-2ゲーム予想の証明など、いくつかの証明への進展が見られました。