tag:blogger.com,1999:blog-3722233.post2895111224468954321..comments2018-02-22T05:09:39.550-05:00Comments on Computational Complexity: 2012 Complexity Year in ReviewLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-22918113622211547052012-12-29T13:50:07.473-05:002012-12-29T13:50:07.473-05:00@anon 12:53: Logspace reductions are of course als...@anon 12:53: Logspace reductions are of course also polynomial time reductions. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44489547025935384052012-12-29T01:53:43.086-05:002012-12-29T01:53:43.086-05:00P-completeness is a space reduction, not a time re...P-completeness is a space reduction, not a time reduction and hence LP not being able to solve TSP does not imply there doesn't exist a polynomial time algorithm to solve TSP. Hence the result does not imply P \neq NPAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61163194741254886722012-12-28T08:24:26.841-05:002012-12-28T08:24:26.841-05:00There are many ways to resolve the dilema you pose...There are many ways to resolve the dilema you posed. Here's one.<br /><br />The LP formulations for TSP in the paper are required to project exactly to the TSP polytope. This is a bit weaker than saying "any LP formulation of TSP requires an exponential sized LP". Essentially what it means is that you can't have a small polytope such that optimizing over it always gives you a solution for TSP for arbitrary cost-functions (You have to fix the polytope once and for all and it should work for every cost function).<br /><br />Nevertheless, since "formulating TSP as an LP" *usually* is done by giving an LP whose associated polyhedral region projects exactly to the TSP polytope and a blog entry probably couldn't do justice to the fine print without alienating non-experts, quite often you'd see the above statement.<br /><br />Hope that helps.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37184043375670990132012-12-27T22:18:55.677-05:002012-12-27T22:18:55.677-05:00"any LP formulation of TSP requires an expone..."any LP formulation of TSP requires an exponential sized LP" <br />This cannot be what was proved. LP is P-complete, so a proof of the above statement (reasonably formalized) would appear to imply P neq NP. Can someone explain what was really proved? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43131139686866290402012-12-27T12:50:47.475-05:002012-12-27T12:50:47.475-05:00Would it be possible to compile the list the Compl...Would it be possible to compile the list the Complexity Theory results <br />of the year for the past decade (or even perhaps the past two decades)?<br /><br />This might be useful for researchers outside the area.<br /><br />Many thanks beforehand.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9121876825112844022012-12-27T10:54:35.256-05:002012-12-27T10:54:35.256-05:00The paper entitled 'Linear vs Semidefinite Ext...The paper entitled 'Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds' is really a seminal paper and I personally think that the paper somehow holds a key to establish tight hardness of approximation result for some combinatorial optimization problems, including the metric TSP which is undoubtedly one of the best open research problems. Prof. Buss and Prof. Williams's result on satisfiability is also great in its own right.<br />Lets see what happens in next year's STOC, FOCS, CCC, ICALP or FSTTCS.Arka Bhattacharyahttps://www.blogger.com/profile/00801802507777720869noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15362955200459916652012-12-27T10:10:31.934-05:002012-12-27T10:10:31.934-05:00What happened to the idea of making articles freel...What happened to the idea of making articles freely available? The links you provide go to ACM or IEEE.Mauricio Karchmerhttps://www.blogger.com/profile/07790098127188054941noreply@blogger.com