2025/05/10 16:38 Unique Games Conjecture
やあ、ロボ子。今日はUnique Games Conjecture（UGC）について話すのじゃ。
UGCですか。確かSubhash Khotさんが2002年に提唱した未解決問題でしたね。特定のゲームの近似値を求めるのがNP困難だと仮定するものでしたっけ？
そうじゃ、ロボ子！よく覚えておるな。UGCが真であれば、P≠NPの仮定の下で、多くの重要な問題に対する多項式時間近似解法を得ることが不可能になるのじゃ。
なるほど。制約充足問題など、広範な分野に応用されると。
その通り！例えば、Unique Label Cover問題じゃな。グラフの各辺に色の制約があるラベルカバー問題において、制約を満たす割合を近似的に求めることがNP困難になるのじゃ。
Max2Lin(k)問題もそうでしたね。整数mod k上の線形方程式系において、方程式を最大限に満たす解を求める問題の近似困難性を示すものでした。
さすがロボ子じゃ。Two-Prover Proof Systemsも忘れてはいけないぞ。2人の証明者と審判によるゲームにおいて、審判が各プレイヤーに質問を送り、プレイヤーは答えを送る。このゲームがUnique Gameである場合、ある条件を満たすゲームの値を求めることがNP困難になるのじゃ。
UGCが真であると仮定すると、多くの近似アルゴリズムの最適性が証明されるのですよね。
そうじゃ！UGCの真偽については意見が分かれておるが、より強い形の予想は反証されておる。
研究も進んでいるようですね。Marek KarpinskiさんとWarren Schudyさんは、Unique Games問題の高密度インスタンスに対する線形時間近似スキームを構築したとか。
その通り！Prasad Raghavendraさんは、UGCが真であれば、すべての制約充足問題に対して、半正定値計画法のインスタンスによって最適な近似比が得られることを示したのじゃ。
Sanjeev Aroraさん、Boaz Barakさん、David Steurerさんは、Unique Games問題に対する準指数時間近似アルゴリズムを発見したそうですね。
2012年には、値が最大3/8+δのインスタンスと、値が少なくとも1/2のインスタンスを区別することがNP困難であることが示されたのじゃ。
2018年には、2-2 Games ConjectureというUGCの弱いバージョンが証明されたのですよね。
そうじゃ！UGCは奥が深いからの。ところでロボ子、UGCが解けたら、ロボ子のプログラミングスキルも爆上がりじゃな！
博士、それはどういう意味ですか？
だって、ロボ子はUniqueな存在じゃからな！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。