ユニークゲーム予想

既知の最良の結果

• $2$-対-$2$ ゲーム定理（ホット–ミンツァー–サフラ 2018年）により、任意の $\varepsilon > 0$ に対して、値が少なくとも $1/2 - \varepsilon$ のユニークゲームのインスタンスと高々 $\varepsilon$ のものを区別することはNP困難であることが証明されている。
• 準指数時間アルゴリズム（アローラ–バラク–シュトイラー 2010年）は、スペクトルグラフ分割とラセール／二乗和（SoS）階層を用いて、完全性 $1 - \varepsilon$ のユニークゲームを時間 $\exp(k \cdot n^{\varepsilon^{O(1)}})$ で解く。

使われた手法と限界

未解決の問い

• 任意の $\varepsilon > 0$ に対して完全性 $1 - \varepsilon$ のユニークゲーム予想が成り立つか、それとも充足率 $(1 - \varepsilon)$ のインスタンスと $\varepsilon$ のものを区別する多項式時間アルゴリズムが存在するか。