News for hackers. Stuff that matters.

A comment on The polynomial algorithm for 3-SAT problem (or P=NP). Parent comment

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by _delirium on Thursday January 20, 2011 @02:53AM (#2123027)
> Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm.

This hasn't been the case in linear programming, at least: 30 years after it was proven to be in P, the old exponential algorithm (the simplex method) is still competitive with the best known polynomial algorithms (interior point methods). From a practical perspective, no real efficiency breakthrough. The fact that there are now two families of algorithms with good performance for the problem is an improvement, but the fact that one of them is theoretically polynomial doesn't seem to have led to dramatic speed gains.

[ Parent | on HN ]
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by mzl on Thursday January 20, 2011 @03:21AM (#2123069)
OTOH, simplex is very efficient already. Average-case complexity for random matrices is polynomial, and there are some interesting results that extend beyond that (see http://arxiv.org/abs/cs/0111050).
[ Parent | on HN ]