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)
“Americans, unhappily, have the most remarkable ability to alchemize all bitter truths into an innocuous but piquant confection and to transform their moral contradictions, or public discussion of such contradictions, into a proud decoration, such as are given for heroism on the battle field.”
—James Baldwin (1924–1987)
“The literal alternatives to [abortion] are suicide, motherhood, and, some would add, madness. Consequently, there is some confusion, discomfort, and cynicism greeting efforts to “find” or “emphasize” or “identify” alternatives to abortion.”
—Connie J. Downey (b. 1934)