Subhash Khot and the Unique Games Conjecture(simonsfoundation.org)
simonsfoundation.org
Subhash Khot and the Unique Games Conjecture
http://www.simonsfoundation.org/quanta/20140812-a-grand-vision-for-the-impossible/
5 comments
Feel humbled to read about him. Floored!
Khot was one of my favorite professors at NYU and always lead on with way better and more in depth stories than the material presented initially. So great to read about his other successes.
Further reading: http://en.wikipedia.org/wiki/Unique_games_conjecture
I'm sort of curious about the scope of UGC. There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard, so how much harder does a problem have to be to invoke UGC? Is there a no-go result that prevents "translating" TSP approximations to the approximation of other problems?
> There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard
Actually, it's either not NP-hard, or not approximable, depending on your definition of TSP. Let me clarify.
TSP, as most people define it, means "given a graph, find the shortest roundtrip". As you rightly state, this problem can be well approximated. But it's not a decision problem (it doesn't have a yes/no answer), and thus doesn't even fit into categories like "NP" or "NP-complete". Talking about the NP-completess of this "Optimization TSP" is essentially a type error.
It's only when we define a "Decision TSP" problem that we can talk about things like NP-hardness. For example, we might ask "Given a graph and a number c, is there a roundtrip of length less than c?". And this new problem is NP-hard. Given any problem in NP, like a SAT instance for example, we can efficiently construct a (usually very contrived) graph that will have a roundtrip of a certain length if and only the original SAT instance is satisfiable.
But unlike "Optimization TSP", this "Decision TSP" can't be approximated. It doesn't even make sense to talk about approximations: a roundtrip of length < c can't "almost exist", the answer is always either yes or no. And while an exact solution for Optimization TSP can trivially answer Decision TSP, any approximation of Optimization TSP is essentially useless in solving Decision TSP.
That's why TSP (in its optimization form) can be easy to approximate, while also (in its decision form) being NP-hard.
Actually, it's either not NP-hard, or not approximable, depending on your definition of TSP. Let me clarify.
TSP, as most people define it, means "given a graph, find the shortest roundtrip". As you rightly state, this problem can be well approximated. But it's not a decision problem (it doesn't have a yes/no answer), and thus doesn't even fit into categories like "NP" or "NP-complete". Talking about the NP-completess of this "Optimization TSP" is essentially a type error.
It's only when we define a "Decision TSP" problem that we can talk about things like NP-hardness. For example, we might ask "Given a graph and a number c, is there a roundtrip of length less than c?". And this new problem is NP-hard. Given any problem in NP, like a SAT instance for example, we can efficiently construct a (usually very contrived) graph that will have a roundtrip of a certain length if and only the original SAT instance is satisfiable.
But unlike "Optimization TSP", this "Decision TSP" can't be approximated. It doesn't even make sense to talk about approximations: a roundtrip of length < c can't "almost exist", the answer is always either yes or no. And while an exact solution for Optimization TSP can trivially answer Decision TSP, any approximation of Optimization TSP is essentially useless in solving Decision TSP.
That's why TSP (in its optimization form) can be easy to approximate, while also (in its decision form) being NP-hard.
Great description. Obviously codeflo knows this, but it's worth pointing out that "roundtrip" means "visiting every city exactly once". Euclidean problem geometry guarantees it (it's always faster to go directly) but many problems, even though emerging from seemingly euclidean space, do not have this property - e.g. if you're using a car, the road network might induce non-euclidean distance geometry that would make the fast roundtrip include more than one visit to a node.
Actually general version of TSP (optimization problem) cannot be approximated to a constant factor in polynomial time unless P = NP. [1]
Your confusion likely stem from the fact that metric-TSP (a special case of TSP problem where the distance between cities form a metric [2]) is actually APX-complete, which means it can be approximated to a constant factor in polynomial time (Christofides algorithm, approx ratio = 1.5).
PS: A potentially interesting aside - Sanjeev Arora, the PhD advisor of Subhash Khot actually got his first Gödel prize (2001) for discovering a PTAS (polynomial time approximation scheme, which in layman term means you can approximate it as close to real answer (but not exactly) as you like in polynomial time) for Euclidean-TSP (independently discovered by Joseph S. B. Mitchell as well). The algorithm make pretty interesting use of Dynamic programming, and was a surprise for the theoretical CS community that time.
[1] Brief intuition - HAMILTON-PATH (decision version) can be solved exactly in polynomial time using a constant factor poly time approximation of general TSP (optimization). But since, HAMILTON-PATH is proven to be NP-Complete, then P must equal NP (in which case we can solve all problems in NP and their optimization counterparts exactly in polynomial time anyway). For a formal proof see Khot's lecture notes: http://www.cs.nyu.edu/~khot/lec1.ps (you can find a variety of other similar resources as well, as this is one of the first impossibility proof in almost any graduate level approximation algorithm class).
[2] http://en.wikipedia.org/wiki/Metric_(mathematics)
Your confusion likely stem from the fact that metric-TSP (a special case of TSP problem where the distance between cities form a metric [2]) is actually APX-complete, which means it can be approximated to a constant factor in polynomial time (Christofides algorithm, approx ratio = 1.5).
PS: A potentially interesting aside - Sanjeev Arora, the PhD advisor of Subhash Khot actually got his first Gödel prize (2001) for discovering a PTAS (polynomial time approximation scheme, which in layman term means you can approximate it as close to real answer (but not exactly) as you like in polynomial time) for Euclidean-TSP (independently discovered by Joseph S. B. Mitchell as well). The algorithm make pretty interesting use of Dynamic programming, and was a surprise for the theoretical CS community that time.
[1] Brief intuition - HAMILTON-PATH (decision version) can be solved exactly in polynomial time using a constant factor poly time approximation of general TSP (optimization). But since, HAMILTON-PATH is proven to be NP-Complete, then P must equal NP (in which case we can solve all problems in NP and their optimization counterparts exactly in polynomial time anyway). For a formal proof see Khot's lecture notes: http://www.cs.nyu.edu/~khot/lec1.ps (you can find a variety of other similar resources as well, as this is one of the first impossibility proof in almost any graduate level approximation algorithm class).
[2] http://en.wikipedia.org/wiki/Metric_(mathematics)
Yes. TSP is NP-complete, which means that exact solutions to TSP can be turned into exact solutions to any other NP problem in P time. However, there is no guarantee on how this transformation behaves on non-exact solutions. In fact, there are many problems that are known to be non-approximable. For example, Vertex Cover is known not to have approximation algorithms better than a factor of 1.3 or so (assuming P != NP). Maximum clique is completely inapproximable (it is impossible to approximate it to any constant factor).
Comic Sans killed it