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:
“Opinions are formed in a process of open discussion and public debate, and where no opportunity for the forming of opinions exists, there may be moods—moods of the masses and moods of individuals, the latter no less fickle and unreliable than the former—but no opinion.”
—Hannah Arendt (1906–1975)
“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)
“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)