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:
“The virtue of dress rehearsals is that they are a free show for a select group of artists and friends of the author, and where for one unique evening the audience is almost expurgated of idiots.”
—Alfred Jarry (1873–1907)
“As long as lightly all their livelong sessions,
Like a yardful of schoolboys out at recess
Before their plays and games were organized,
They yelling mix tag, hide-and-seek, hopscotch,
And leapfrog in each other’s way all’s well.”
—Robert Frost (1874–1963)
“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)