[Computational Complexity] UG-Hard
We have seen many exciting papers based on the unique games conjecture for example that improving the Goemans-Williamson approximation algorithm for Max-Cut would imply P=NP if the unique games conjecture is true.
Many complexity theorists have told me that they have doubts and in some cases outright don't believe the unique games conjecture. What good are results based on a conjecture that complexity theorists won't stand behind?
The unique games conjecture states that a certain unique games problem is NP-complete. Even if unique games is not NP-complete, it still might be difficult to solve, a situation we believe for some other famous problems like factoring, graph isomorphism and Nash equilibrium. We've seen hardness results based on reductions from these later problems so perhaps we can do the same for unique games.
Most, if not all, of the theorems based on the unique games conjecture actually prove something stronger, they reduce the unique games problem to the approximation problem, e.g., improving the Goemans-Willamson bound would yield an algorithm that solves the unique games problem.
Let me suggest the term UG-Hard for the class of problems to which we can reduce the unique games problem. Theorem: Improving the Goemans-Williamson algorithm for Max-cut is UG-Hard. No conjectures necessary.
If the unique-games conjecture is true, the UG-hard is the same as NP-hard. If unique games are not solvable in polynomial-time then the UG-hard problems will not have a polynomial-time algorithm. And as long as we don't have a polynomial-time algorithm for unique game then finding an efficient algorithm for any UG-hard problem would imply settling the now major open question of the complexity of the unique games.
Posted by Lance to Computational Complexity at 12/11/2005 07:03:00 AM