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.
Am I the only one who simply doesn't believe that graph isomorphism is hard?
ReplyDeleteLance,
ReplyDeleteThe UnderGrads in my place have classified many problems as UG-Hard. So, can you please suggest some other name:)?
It seems that Knuth once asked the theorists of that time, a name for what we now call as NP-C problems. Someone (I think Larry Stockmeyer) suggested that we call them as HardAsS problems : for Hard As SAT.
Amar
I like the "UG-hard" name. It is compatible with naming convention used elsewhere, such as "3SUM-hardness".
ReplyDeletePiotr
Oh yes, and we can tell undergrads that UG stands for undergraduates. This should motivate them to solve the problem :)
ReplyDeletePiotr
People have a variety of opinions about the conjecture and because of this the term "unique games-hard" is already in somewhat common usage. Muli Safra has staked money on the problem lying strictly between P and NPC.
ReplyDeleteOthers have suggested that perhaps unique games captures the complexity of the semi-definite programming model, which is why the hardness techniques always relate very closely to an integrality gap for some SDP.
This is also why the Khot-Vishnoi paper was so nice; the story is almost more important than the result. Proving UG-hardness for sparsest cut led to an unconditional integrality gap example which suggests that the UG problem is capturing something substantial.
"UG-hard" is good terminology; moreover, it naturally raises a question that the current UG-hardness results don't address: Which of these UG-hard problems are UG-complete?
ReplyDeleteI suggest calling it the Unique Games Hypothesis, and therefore refer to
ReplyDeleteUGH-hard and UGH-complete problems.
I suggest calling it the Unique Games Hypothesis, and therefore refer to
ReplyDeleteUGH-hard and UGH-complete problems.
This is exactly the kind of thing that Lance's proposal is meant to avoid. There is no 'hypothesis' needed.