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 exist few things more tedious than a discussion of general ideas inflicted by author or reader upon a work of fiction.”
—Vladimir Nabokov (1899–1977)
“Clearly, society has a tremendous stake in insisting on a woman’s natural fitness for the career of mother: the alternatives are all too expensive.”
—Ann Oakley (b. 1944)