tag:blogger.com,1999:blog-3722233.post1172020541192277799..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: Favorite Theorems: Extended FormulationsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-79872131986669592902014-04-11T11:32:06.913-05:002014-04-11T11:32:06.913-05:00Kaibel and Weltge have found a new, very short pr...Kaibel and Weltge have found a new, very short <a href="http://arxiv.org/abs/1307.3543" rel="nofollow"> proof </a> 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. Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21315937662384540552014-04-10T08:45:02.244-05:002014-04-10T08:45:02.244-05:00There are a couple of subtleties here. In short, h...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.Sebastian Pokuttahttp://www.pokutta.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90736028055541490692014-04-10T08:26:52.300-05:002014-04-10T08:26:52.300-05:00TSP is naturally formulated as the optimization of...TSP 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. <br /><br />This 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. <br />Ronald de Wolfhttp://homepages.cwi.nl/~rdewolf/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66042916153496502302014-04-10T02:19:10.044-05:002014-04-10T02:19:10.044-05:00I'm confused. I thought LP was P-complete and ...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.Anonymousnoreply@blogger.com