Unsolved problem in computational complexity theory
Unsolved problem in computer science:
Is the Unique Games Conjecture true?
(more unsolved problems in computer science)
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002.[1][2][3] The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP,[4] then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
The conjecture is unusual in that the academic world seems about evenly divided on whether it is true or not.[1]
^ abKlarreich, Erica (October 6, 2011), "Approximately Hard: The Unique Games Conjecture", Simons Foundation, retrieved 2012-10-29
^Lipton, Dick (May 5, 2010), "Unique Games: A Three Act Play", Gödel’s Lost Letter and P=NP, retrieved 2012-10-29
^Cite error: The named reference khot02onthepower was invoked but never defined (see the help page).
^The unique games conjecture is vacuously true if P = NP, as then every problem in NP would also be NP-hard.
and 26 Related for: Unique games conjecture information
Is the UniqueGamesConjecture true? (more unsolved problems in computer science) In computational complexity theory, the uniquegamesconjecture (often...
the field of computational complexity, and is best known for his uniquegamesconjecture. Khot received the 2014 Rolf Nevanlinna Prize by the International...
it cannot be approximated up to a factor smaller than 2 if the uniquegamesconjecture is true. On the other hand, it has several simple 2-factor approximations...
the uniquegamesconjecture, another unproven computational hardness assumption according to which accurately approximating the value of certain games is...
versus NP. Game complexity List of unsolved problems in mathematics Uniquegamesconjecture Unsolved problems in computer science A nondeterministic Turing...
= NL problem PH = PSPACE problem L = P problem L = RL problem Uniquegamesconjecture Is the exponential time hypothesis true? Is the strong exponential...
an inapproximability result that can be strengthened under the uniquegamesconjecture. For tournament graphs, the minimum feedback arc set can be approximated...
astronomical catalogue of galaxies UGC, a codon for cysteine Uniquegamesconjecture, a conjecture in computational complexity User-generated content, media...
expectation the ratio is always at least 0.87856.) Assuming the uniquegamesconjecture, it can be shown that this approximation ratio is essentially optimal...
strategy gives the best possible polynomial-time approximation if the uniquegamesconjecture is true. It is also possible to use semidefinite programming or...
_{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.} If the uniquegamesconjecture is true, this is the best possible approximation ratio for maximum...
to better than f − 1 − ϵ {\displaystyle f-1-\epsilon } . If the Uniquegamesconjecture is true, this can be improved to f − ϵ {\displaystyle f-\epsilon...
geometry. It has also been suggested to have connections to the uniquegamesconjecture in computational complexity theory. Oliver Lorscheid, along with...
algorithm with an approximation factor of 2. Under the recent uniquegamesconjecture, this factor is even the best possible one. NP-hard problems vary...
the problem appears to be much harder to approximate. Under the uniquegamesconjecture, an unproven but commonly used computational hardness assumption...
are based on other hypotheses, a notable one among which is the uniquegamesconjecture. Since the early 1970s it was known that many optimization problems...
of California at Berkeley. Raghavendra showed that assuming the uniquegamesconjecture, semidefinite programming is the optimal algorithm for solving...
d-hitting set permits a d-approximation algorithm. Assuming the uniquegamesconjecture, this is the best constant-factor algorithm that is possible and...
optimality of the Goemans–Williamson MAX-CUT algorithm (assuming the UniqueGamesConjecture), with Subhash Khot, Guy Kindler and Ryan O’Donnell. Mossel has...
cubic graph? The reconstruction conjecture and new digraph reconstruction conjecture on whether a graph is uniquely determined by its vertex-deleted...
Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the uniquegamesconjecture. This implication, due to Khot et al., was the impetus behind proving...
Global Information