AtlasFor ALignmenTOpen Atlas
← 審査済みの問い

審査済み

ユニークゲーム予想は正しいか？

Is the Unique Games Conjecture true?

computer-sciencecomputational-complexityapproximation

問題文

小さな定数の任意の組について、ほぼ充足可能なユニークゲームの事例と、充足からほど遠い事例を区別することが NP 困難か、を決定せよ。

Decide whether, for every pair of small constants, it is NP-hard to distinguish unique games instances that are nearly satisfiable from those that are far from satisfiable.

背景

If true, the conjecture pins down the exact approximation threshold of a long list of optimisation problems. Half of it - the 2-to-2 games case - is now a theorem, and a subexponential algorithm is known for the general case.

アプローチ · 2 件

解決したかどうかは、問いではなくアプローチごとに決まります。Atlas は判定しません。外部の判定者が何をしたかを記録します。

  • Hardness reductions from PCP machinery

    査読付きの証明

    到達状況
    進行中
    判定者
    the complexity theory community, through journal peer review · 査読
    定式化
    Build a probabilistically checkable proof system whose soundness analysis yields the unique games hardness gap.問いと同値

    保たれているもの

    • Would establish the conjecture as stated

    弱まっているもの

    • The 2-to-2 games theorem gives the conjecture with imperfect completeness, which is strictly weaker

    加えられた仮定・条件

    • Grassmann graph expansion machinery

    証拠

    • preprintarXiv:1804.08662S. Khot, D. Minzer, M. Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion (2018): proves the 2-to-2 games conjecture, i.e. half of the Unique Games Conjecture

  • Algorithms for unique games

    計算による判定

    到達状況
    進行中
    判定者
    execution and peer review: a fast enough algorithm would refute the conjecture · 査読
    定式化
    Solve unique games faster than any NP-hard problem should be solvable, refuting the conjecture.問いと同値

    保たれているもの

    • Would settle the question in the negative

    弱まっているもの

    • The known algorithm is subexponential, not polynomial, so it does not refute the conjecture

    加えられた仮定・条件

    • Nothing

    閉じた道

    • A subexponential algorithm for unique games exists, so the conjecture cannot be proved by any reduction that preserves exponential-time hardness; hardness proofs must lose that structure.条件つき（the Exponential Time Hypothesis）— 前提が崩れれば道は開く
      • paperdoi:10.1145/2775105S. Arora, B. Barak, D. Steurer, Subexponential algorithms for unique games and related problems, J. ACM 62 (2015), art. 42

    証拠

    • paperdoi:10.1145/2775105S. Arora, B. Barak, D. Steurer, Subexponential algorithms for unique games and related problems, J. ACM 62 (2015), art. 42

出典

  • paperdoi:10.1145/509907.509985S. Khot, On the power of unique 2-prover 1-round games, STOC 2002, 767-775: the original conjecture
  • preprintarXiv:1804.08662S. Khot, D. Minzer, M. Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion (2018): proves the 2-to-2 games conjecture, i.e. half of the Unique Games Conjecture

記録

URI
https://atlasalt.com/q/b57ab221-3da6-4fc4-897d-6f1830daff0e
登録
2026-09-17
最終レビュー
2026-09-19
次回レビュー期限
2026-12-18
版
4e7f67c892c8
ライセンス
CC-BY-4.0
立場
record_only（Atlas は判定しない）