tag:blogger.com,1999:blog-3722233.post113534927665564262..comments2021-04-20T09:52:56.297-05:00Comments on Computational Complexity: All I Want for Christmas is a Proof that P≠NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-76117410621627013362007-11-27T08:24:00.000-06:002007-11-27T08:24:00.000-06:00id like to begin to my question with many apologie...id like to begin to my question with many apologies <BR/>i am an electrical engineering student dealing with optimization in my project. I need to find the best method for solving quadratic programming problem with constraints. Up to now I found active set method, simplex and interior point. From the complexity view of the methods seems interior point is the best one. Is it true? is there a nother type of algorithm?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136293575707294562006-01-03T07:06:00.000-06:002006-01-03T07:06:00.000-06:00"All I Want for Christmas is a Proof that P?NP"For..."All I Want for Christmas is a Proof that P?NP"<BR/><BR/>For 2006 ... be nice. I have several elves randomly typing on PCs. Other elves have designed a Turing enumerator for generating proofs. What else can I do? Help me help you!<BR/><BR/>Dr. S. Claus.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135620109510175122005-12-26T12:01:00.000-06:002005-12-26T12:01:00.000-06:00I think there are some misconceptions in the above...I think there are some misconceptions in the above posts about the Kelner-Spielman algorithm that ought to be remedied.<BR/><BR/>1. The perturbation to avoid degeneracy that they use does not introduce any additional dependence on the precision of the inputs. As noted in Megiddo's original paper, it can be performed purely formally in terms of a symbolic parameter. The only reason that their algorithm isn't strongly polynomial is that it has to repeatedly revise the probability distribution that it uses for its simplex pivots, and the number of times that it needs to do so depends on the bit-length of the input. It is not obvious that this dependency can be eliminated, but it is also not obvious that it cannot be (by a different pivot rule). This seems to be real progress towards a strongly polynomial algorithm. In particular, it provides a combinatorial algorithmic approach that can work without proving the Hirsch conjecture. This removes a big roadblock...<BR/><BR/>2. Their algorithm really is a simplex algorithm. They don't walk along the *feasible* vertices of a single polytope, but they do walk along the potential (feasible or infeasible) vertices of a single polytope. Many other simplex algorithms attempt to do this too (e.g., the self-dual simplex method). It's just that nobody had previously been able to design such an algorithm to run in poly time. The geometric stuff that the poster said looked like ellipsoid appeared in the analysis, not in the algorithm--the algorithm really is just a sequence of combinatorial pivots.<BR/><BR/><BR/>Independently of the question of strong polynomiality, it has been a very long open question whether any simplex method can run in poly time. Their paper resolves that, which is really exciting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135601604482857382005-12-26T06:53:00.000-06:002005-12-26T06:53:00.000-06:00Isn't the Kelner-Spielman algorithm closer to elli...Isn't the Kelner-Spielman algorithm closer to ellipsoid than it is to simplex? I mean, in the ellipsoid algorithm, you guess a bound on the optimal solution (which is where the dependence on input numbers comes in) and then check for feasibility. Here, (I think) they guess a bound on the optimal solution and then check for feasibility via boundedness. A real "simplex" algorithm should have the property that it takes some series of steps along a single polytope. I see how their algorithm is related to a simplex like algorithm, but I really don't see how it can be called a simplex algorithm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135460011251647242005-12-24T15:33:00.000-06:002005-12-24T15:33:00.000-06:00Happy Holidays Lance,Thanks for a great year of bl...Happy Holidays Lance,<BR/>Thanks for a great year of blogging!<BR/>AmarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135416187980394362005-12-24T03:23:00.000-06:002005-12-24T03:23:00.000-06:00"...but maybe Santa will come through for us in ti..."...but maybe Santa will come through for us in time for next Christmas"<BR/><BR/>Then it won't be Christmas, it will be Armageddon.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135396429071714612005-12-23T21:53:00.000-06:002005-12-23T21:53:00.000-06:00I think Christmas and Chanukah land on the same da...I think Christmas and Chanukah land on the same day every 19 years.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135354602815358592005-12-23T10:16:00.000-06:002005-12-23T10:16:00.000-06:00The Kelner-Spielman paper is greatbut I think peop...The Kelner-Spielman paper is great<BR/>but I think people should <BR/>know the following. There are <BR/>two main reasons for people's <BR/>interest in poly-time simplex type algorithms. <BR/>The first is to explain why simplex<BR/>performs so well on many real-world<BR/>problems. Second, simplex seems to<BR/>be the only candidate that<BR/>could lead to a strongly polynomial <BR/>time algorithm for LP, this being<BR/>the main theoretical motivation. Unfortunately<BR/>the Kelner-Spielman paper does<BR/>several things in addition to<BR/>running the shadow vertex simplex<BR/>that causes a dependence on numbers.<BR/>They have to avoid degeneracy which<BR/>is explicitly introduced by their<BR/>approach, by doing perturbation. <BR/>They need to sample implicity<BR/>from an affine transformation that<BR/>makes the polytope rounded. Both<BR/>steps cause the algorithm to <BR/>depend on the bits of the matrix<BR/>and it is unclear how this<BR/>can be avoided by their approach.<BR/><BR/>It is nice cute paper following <BR/>some geometric ideas in <BR/>Spielman-Teng smoothed analysis <BR/>for LP. However, there is some<BR/> danger here that<BR/>people might think that the <BR/>main problem is solved. It doesn't<BR/>seem that way (IMHO). It would<BR/>be nice if other more knowleadgeable<BR/>folk can add to the discussion.Anonymousnoreply@blogger.com