Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem. I wrote on this before, and bewailed the fact that I was not smart enough to figure out there was a general theorem there: Yannakakis showed that no symmetric linear programming formulation of polynomial size can formulate the TSP. The “symmetric” part of the theorem was always bothersome since it seemed an unnecessary addition. You can make a symmetric formulation “unsymmetric” by doing something goofy in adding a useless variable or similar, but the fundamental result still holds. Can asymmetry work on a fundamental level? I worked on trying to remove the symmetric assumption, but had no success. That’s not surprising since Yannakakis clearly would have not included the requirement if it was easy to remove. Yannakakis is smarter than Trick. Therefore Trick cannot remove the requirement. Q.E.D. But I still tried for a while.
Fortunately, research moves on, and people learn more and more, and finally enough gets proved that smart people can figure out how to move forward. It appears that the symmetric requirement can be removed. Sebastian Pokutta, and his coauthors Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronal de Wolf have a paper that proves that any linear programming formulation (symmetric or not) of the TSP is exponentially sized super polynomial. Sebastian’s blog post has a very nice description of some recent history (including the astonishing result that sometimes the symmetry requirement does matter) and gives pointers to both the paper and to some slides. I have not had time to go through things thoroughly (or at all, really) but the paper seems a trove of interesting results. I feel like starting a Ph.D. seminar next week to study it!
Between Bill Cook’s soon-to-be-released TSP book and this news, 2012 is shaping up to the be the year of the Traveling Salesman Problem!
Intro states: “Therefore, it is impossible to prove P = NP by giving a polynomial-size LP for any of these problems.” But LP is P-complete so how they can prove “there are no polynomial-size LPs for TSP” without also proving P != NP or NP not in P/poly?
@confused, there are two reasons: (1) Just because an LP is exponential in size, that doesn’t mean that it can’t be solved in polynomial time (c.f. Edmonds algorithm for max-weight matching, which uses a primal-dual approach). (2) Whatever property the LP has, there may be some other algorithmic approach that would lead to a polynomial algorithm.
So this is essentially a negative result. It rules out proving P=NP by writing down a polynomial-sized LP representation. But it doesn’t rule out proving P=NP.
Just to nitpick a little, the claim is that every LP formulation of the TSP is superpolynomial. That’s not quite exponential–as I understand it, if the power is sublinear, the whole expression is subexponential, but if the power is super-logarithmic, then the whole expression is superpolynomial. The TSP result is that LPs are at least of size 2^{n^{1/4}}.
Every problem in P can be efficiently reduced to instances of LP of polynomial-size, because LP is P-complete. Hence if P=NP then every TSP instance could be formulated as a “polynomial-size LP” in a precise sense. So it is confusing to say that there is no polynomial-size LP for TSP. There are additional assumptions on the kind of LP being studied.
@confused When you are talking about decision problems (and when you are talking about P-completeness, you do), each problem in P that allows for both YES and NO-instances, is P-complete. If you want to reduce a problem-instance to a LP, you just run the polynomial time algorithm (which exists, since your problem is in P) on your instance. If the answer is YES, you return a trivial YES-instance of LP. Otherwise, you return a trivial NO-instance. Therefore, your “precise sense” statement is much stronger than just P-completeness.
@confused (or anybody), maybe you can clarify something for me.
Thinking of matching again, nonbipartite matching (cardinality or weighted) is clearly in P, but the description of the convex hull of incidence vectors of matchings when the variables represent edges has exponentially many constraints. I suppose there must be a polynomial-sized LP that represents the matching problem, but I don’t know what the decision variables would be. One approach would be some sequence of reductions to other problems in P. I don’t know if it’s been done.
For the TSP, the usual variables are edges and the polytope is the convex hull of incidence vectors of tours. But we know the description of that polytope is exponential because it needs the subtour elimination constraints. So other LP descriptions (e.g. Swart’s) must involve other variables. I don’t remember enough about Swart to know what they were.
Can anybody shed more light here?
I don’t want to leave this discussion hanging, so I spent a few minutes with Papadimitriou’s _Computational_Complexity_. I haven’t really nailed down all the details, but my surface understading is this.
When we talk about NP, the reductions we use are polytime reductions. A problem is NPC if every NP problem is polytime reducible to it. Polytime reductions aren’t very interesting when inside P for the reason @Paul explains. So hardness in P and P-completeness are going to involve something else.
Very briefly, hardness in P has to do with how parallelizable an algorithm is–P-complete problems are the least parallelizable problems in P–they appear to be inherently sequential. Reductions from one problem to another in P are logspace reductions rather than polytime. There’s a hierarchy of parallelizability inside P that would collapse if a P-complete problem turned out to be parallelizable.
I’m not quite sure yet, but I suspect that all renders @confused’s question and mine moot.
Thinking of matching again, nonbipartite matching (cardinality or weighted) is clearly in P, but the description of the convex hull of incidence vectors of matchings when the variables represent edges has exponentially many constraints. I suppose there must be a polynomial-sized LP that represents the matching problem, but I don’t know what the decision variables would be. One approach would be some sequence of reductions to other problems in P. I don’t know if it’s been done.
This is an easy exercise in complexity theory. Take a polynomial time algorithm for nonbipartite matching on unweighted graphs, so it takes n^2-bit input. Convert that to a polynomial size Boolean circuit which outputs 1 iff the input has a perfect matching (for example). That circuit can be transformed into an LP, where n^2 of the variables correspond to the input adjacency matrix, and the other polynomially many variables correspond to the gates of the circuit. This LP is feasible iff the n^2 edge variables correspond to a graph with a perfect matching. (Would be surprised if the circuit-to-LP reduction isn’t in Papadimitriou.)
Of course P-completeness doesn’t use polynomial-time reductions, but a weaker reducibility notion (typically logspace). That doesn’t affect my original point at all.
Look at Papadimitriou p.354, last paragraph, for another version of my point: “Yannakakis points out that a general non-symmetric polynomial LP for telling whether a graph has a Hamiltonian cycle exists if and only if NP has polynomial circuits.”
I’m not sure about the “easy exercise in complexity theory”.
See Rothvoss (2011) http://arxiv.org/abs/1105.0036 . “Yannakakis [Yan91] showed that the TSP
polytope PTSP (the convex full of the characteristic vectors of all Hamiltonian
cycles in the complete graph on n nodes) does not have a subexponential
size symmetric formulation. Surprisingly the same result holds true for
the matching polytope, though here a complete description of all facets is
known due to Edmonds [Edm65] and the problem itself as well as the separation
problem are solvable in polynomial time.”
…
“However, it remains a fundamental open problem to show that the matching
polytope or the TSP polytope do not admit any non-symmetric compact
formulation.”
There is a subtlety here that I can’t unravel. Perhaps the question is better asked on Pokutta’s blog?
And the reply is up on Pokutta’s blog. AIUI, the point is that the polytope of interest for the decision problem (he uses Hamiltonian Cycle, but I think the argument is the same for the decision form of TSP) is a face of the TSP polytope, not the entire thing. Their result doesn’t rule out a polynomial description of the relevant face.