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:
“One must love humanity in order to reach out into the unique essence of each individual: no one can be too low or too ugly.”
—Georg Büchner (1813–1837)
“In 1600 the specialization of games and pastimes did not extend beyond infancy; after the age of three or four it decreased and disappeared. From then on the child played the same games as the adult, either with other children or with adults. . . . Conversely, adults used to play games which today only children play.”
—Philippe Ariés (20th century)
“What these perplexities of my uncle Toby were,—’tis impossible for you to guess;Mif you could,—I should blush ... as an author; inasmuch as I set no small store by myself upon this very account, that my reader has never yet been able to guess at any thing. And ... if I thought you was able to form the least ... conjecture to yourself, of what was to come in the next page,—I would tear it out of my book.”
—Laurence Sterne (1713–1768)