- Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf, STOC 2012 (ArXiv).
- The matching polytope has exponential extension complexity by Thomas Rothvoß. To appear in STOC 2014.
It all started with a paper by E.R. "Ted" Swart (the Deolalikar of the 80's) that claimed to show P = NP by giving a polynomial-time algorithm for Traveling Salesman based on linear programming. Yannakakis put the nail in that technique by showing that no symmetric linear program formulation can solve the traveling salesman problem. The TSP problem expressed as a linear program has many facets (multi-dimensional faces) but one could possibly have a higher dimensional polytope with a smaller number of facets that could project down to the TSP polytope. Yannakakis showed that these higher dimensional symmetric polytopes must still have many facets by showing an equivalence between the smallest number of facets and the monotone dimension of a slack matrix of the polytope describing the TSP.
Not much happened since the 80's until Fiorini et al. generalized the Yannakakis result to give exponential lower bounds on the number of facets of general non-symmetric extensions of the polytope for traveling salesman. They combine Yannakakis' techniques with some communication lower bounds due to Alexander Razborov. Their approach was inspired by quantum computing ideas but in the end they had a more conventional proof.
Last fall Rothvoß showed even stronger exponential lower bounds for the matching polytope through a "substantial modification" of Razborov's work. Since matching is in P, Rothvoß showed that there are polynomial-time computable problems that can be formulated, but not succinctly formulated, as linear programs.
There has also been recent work showing lower bounds approximating clique via linear programs.
Ankur Moitra gave an excellent talk at the recent Dagstuhl giving an overview of these results and the techniques involved. The next step: Show lower bounds for semidefinite programs.
Not much happened since the 80's until Fiorini et al. generalized the Yannakakis result to give exponential lower bounds on the number of facets of general non-symmetric extensions of the polytope for traveling salesman. They combine Yannakakis' techniques with some communication lower bounds due to Alexander Razborov. Their approach was inspired by quantum computing ideas but in the end they had a more conventional proof.
Last fall Rothvoß showed even stronger exponential lower bounds for the matching polytope through a "substantial modification" of Razborov's work. Since matching is in P, Rothvoß showed that there are polynomial-time computable problems that can be formulated, but not succinctly formulated, as linear programs.
There has also been recent work showing lower bounds approximating clique via linear programs.
Ankur Moitra gave an excellent talk at the recent Dagstuhl giving an overview of these results and the techniques involved. The next step: Show lower bounds for semidefinite programs.
I'm confused. I thought LP was P-complete and hence any other problem in P could be succinctly formulated as an LP under logspace reductions.
ReplyDeleteTSP is naturally formulated as the optimization of a a linear function (the length of the Hamiltonian path) over the TSP-polytope, which is the convex hull of all Hamiltonian cycles in the complete graph on n vertices. The result is that every polytope that projects down to the TSP-polytope, has an exponential number of facets (tight linear inequalities). So every LP that explicitly formulates TSP as the optimization of a linear function over a polytope (its feasible set) that projects down to the TSP-polytope, must have exponential size.
DeleteThis does not rule out efficient algorithms that solve TSP via an efficient separation oracle for an implicit exponential-size LP. It also does not rule out poly-size LPs for TSP that (by the P-completeness of LP) would exist if TSP happened to have poly-size circuits; but such polys-size LPs would not project down to the TSP polytope.
There are a couple of subtleties here. In short, however slightly unsatisfactory: Here we ask for the full polytopes and their complexity for representing them as linear programs, not for a *specific* decision problem.
ReplyDeleteKaibel and Weltge have found a new, very short proof for Fiorini et al. result. It is based on a a half-page proof that any covering of the unique disjointness matrix requires (3/2)^n 1-rectangles.The (a,b) entry of this matrix is 1-|a\cap b| if a and b intersect in at most one element, and is * otherwise.
ReplyDelete