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:
“When each thing is unique in itself, there can be no comparison made.... There is only this strange recognition of present otherness.”
—D.H. (David Herbert)
“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)
“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)