Unique games conjecture

From Wikipedia, the free encyclopedia

The Unique Games Conjecture (UGC) is a conjecture in computational complexity theory made by Subhash Khot in 2002.

A "unique game" is a special case of a two-prover, one-round (2P1R) game. A two-player, one-round game has two players (also known as provers) and a referee. The referee sends each player a message drawn from a known distribution, and the players each have to send a response. The players are not allowed to communicate with each other. The players win if the referee accepts their responses, using a known predicate Accept(question 1, question 2, answer 1, answer 2). The game is called a

  • "projection game" if for every response of the first prover there is a unique response by the second prover that causes the referee to accept.
  • "unique game" if it is a projection game in both directions. That is, in addition to being a projection game, it must be the case that for every response of the second prover there is a unique response by the first prover that causes the referee to accept. The acceptance predicate for a unique game is therefore essentially just a permutation of the set of possible responses.
  • "XOR game" if it is a unique game and the response set of each prover is {0,1}. In this case, there are only two possible predicates, either equality or inequality.

The Unique Games Conjecture states that for any fixed ε > 0, there exists a large enough constant p such that it is NP-hard to determine whether, for a unique game with p possible responses from each prover:

  • any assignments of values to the variables will satisfy at most ε fraction of the constraints
  • there exists an assignment of values to the variable which will satisfy at least a (1 − ε) fraction of the constraints

The Unique Games Conjecture is a strengthening of the Probabilistically Checkable Proof (PCP) Theorem. Both the UGC and the PCP theorem have many applications in the theory of complexity of approximation. For example, assuming the UGC, it is NP-hard to approximate the MAX CUT value to better than αGW + ε for any ε > 0, where αGW = 0.878… is the approximation ratio of the Goemanns-Williamson SDP-based algorithm. Without assuming the UGC, it is only known that approximating MAX CUT to a ratio better than 16 / 17 = 0.941… is NP-hard.

[edit] An example of a unique game

Suppose that we have a system of linear equations over the integers modulo p, for a fixed prime p:

x1 \equiv 2\cdot x_2 \pmod{7}
x2 \equiv 4\cdot x_5 \pmod{7}
\vdots
xn \equiv 2\cdot x_7 \pmod{7}

The goal is to solve all of these equations simultaneously. If we cannot do that, we would like to satisfy the largest possible fraction of them.

This game is similar to "2-prover, 1-round" games, which are studied in conjunction with the PCP theorem.

If the system of equations has a solution, it's very easy to find it: we just try one value for x1. This will force all the other variables to have a specific value. If we run into a contradiction, then our initial guess for x1 was incorrect, so we try another one. Since there are only a fixed (assumed to be small) number of choices for the value of x1, we can try them all quickly.

This game is "unique" in the sense that every choice of a value for a variable x forces a unique choice for the value of any variable y that appears in any constraint with x. That is, each constraint can be viewed as a function π mapping values of x to a unique value y = π(x) such that the pair x,y satisfy the constraint.

[edit] Applications

Although it is unknown whether the conjecture is true, it has been shown that if it is true then it is hard to find even approximate solutions for many well-studied problems, such as vertex cover and max cut.

[edit] External links