UG-hard

crypto
ざっくり言うと指数時間掛かる

例えば、Max-CutのGoemans-Williamson近似アルゴリズムを改善すると、ユニーク・ゲーム予想が真であればP=NPになるというような、ユニーク・ゲーム予想に基づいたエキサイティングな論文を多く見てきました。
しかし、多くの複雑性理論家は、ユニークゲーム予想に疑問を持ち、場合によっては全く信じていないと私に言いました。複雑性理論家が支持しないような予想に基づいた結果に何の意味があるのでしょうか？
ユニーク・ゲーム予想とは、あるユニーク・ゲーム問題がNP完全であるというものです。因数分解、グラフ同型性、ナッシュ均衡などの有名な問題がそうであるように、ユニークゲームがNP完全ではないとしても、解くのは難しいかもしれません。これらの問題からの還元に基づく硬さの結果を見たことがありますので、unique gamesについても同じことができるかもしれません。
例えば、Goemans-Willamson境界を改善すれば、ユニークゲーム問題を解くアルゴリズムが得られるというように。
例えば、Goemans-Willamson境界を改善すれば、ユニークゲーム問題を解くアルゴリズムが得られるというように、ユニークゲーム問題を縮小できる問題のクラスをUG-Hardと呼ぶことを提案します。定理です。Max-cutのGoemans-Williamsonアルゴリズムの改良はUG-Hardである。推測は不要。
unique-games conjectureが真であれば、UG-hardはNP-hardと同じである。もしユニークなゲームが多項式時間で解けないなら、UG-hard問題は多項式時間アルゴリズムを持たない。そして、ユニーク・ゲームの多項式時間アルゴリズムがない限り、任意のUGハード問題のための効率的なアルゴリズムを見つけることは、ユニーク・ゲームの複雑さという現在の主要な未解決問題を解決することを意味する。