Kindly comments on The Unique Games Conjecture and FAI: A Troubling Obstacle - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (25)
Some CSPs already have efficient exact or approximate algorithms. (For example, we can approximate Max-Cut to within a factor of 0.878, or test if a graph has a 2-coloring, in polynomial time.) The UGC is normally stated about a single class of CSPs, though I'm sure it has implications for some other classes as well.
The impression I've always gotten was that average-case instances of many NP-complete problems are believed to be tractable. JoshuaZ points out that this may not be true, but it seems from some skimming that results along that direction are less like "a typical instance is hard" and more like "we can generate random hard instances semi-efficiently".
This is interesting from a cryptographical point of view: it would be nice to have a one-way function whose hardness depended on P vs NP rather than a weaker assumption. But if we encounter a constraint satisfaction problem in the real world, it is not going to come even from an adversarially chosen random distribution.
It is, in fact, likely that such a problem will have some additional exploitable structure that will make it easier than the typical instance (which we already don't know is hard). An example of this is metric TSP. This would be the "best case" you're referring to.