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)
“Criticism occupies the lowest place in the literary hierarchy: as regards form, almost always; and as regards moral value, incontestably. It comes after rhyming games and acrostics, which at least require a certain inventiveness.”
—Gustave Flaubert (1821–1880)
“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)