The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the following promise problem (Lyes, Lno) is NP-hard:
- Lyes = {G: the value of G is at least 1 − δ}
- Lno = {G: the value of G is at most ε}
where G is a unique game whose answers come from a set of size k.
Read more about Unique Games Conjecture: Relevance, Discussion and Alternatives
Famous quotes containing the words unique, games and/or conjecture:
“Man’s unique reward, however, is that while animals survive by adjusting themselves to their background, man survives by adjusting his background to himself.”
—Ayn Rand (1905–1982)
“At the age of twelve I was finding the world too small: it appeared to me like a dull, trim back garden, in which only trivial games could be played.”
—Elizabeth Bowen (1899–1973)
“There is something fascinating about science. One gets such wholesale returns of conjecture out of such a trifling investment of fact.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)