Discussion and Alternatives
Currently there is no consensus regarding the truth of the unique games conjecture. Certain stronger forms of the conjecture have been disproved.
A different form of the conjecture postulates that distinguishing the case when the value of a unique game is at least 1 − δ from the case when the value is at most ε is impossible for polynomial-time algorithms (but perhaps not NP-hard). This form of the conjecture would still be useful for applications in hardness of approximation.
The constant δ > 0 in the above formulations of the conjecture is necessary unless P = NP. If the uniqueness requirement is removed the corresponding statement is known to be true by the parallel repetition theorem, even when δ = 0.
In 2010, Arora, Barak and Steurer found a subexponential time approximation algorithm for unique games problem.
Read more about this topic: Unique Games Conjecture
Famous quotes containing the words discussion and, discussion and/or alternatives:
“If the abstract rights of man will bear discussion and explanation, those of women, by a parity of reasoning, will not shrink from the same test: though a different opinion prevails in this country.”
—Mary Wollstonecraft (1759–1797)
“There are answers which, in turning away wrath, only send it to the other end of the room, and to have a discussion coolly waived when you feel that justice is all on your own side is even more exasperating in marriage than in philosophy.”
—George Eliot [Mary Ann (or Marian)
“The last alternatives they face
Of face, without the life to save,
Being from all salvation weaned
A stag charged both at heel and head:
Who would come back is turned a fiend
Instructed by the fiery dead.”
—Allen Tate (1899–1979)