Hacker News Reader

What would be cool, too, would be a proof that yeah, P != NP, sure, but there is an algorithm that can solve any NP-complete problem with a complexity of O((1+Ɛ)^n), with Ɛ very small, so still exponential but solveable in practice in most cases, and we don't know what that algorithm is, we just know it exists.

View on HN

I mean the simplex algorithm practically scales linearly for most of our cases, to the point that we assume today Linear Programming a solved problem. We can solve problems with billions of variables and constraints that create a simplex with an astronomical number of vertices. And we can do all these with out of the box solvers.

Of course the devil is still there, you can find very small problems that completely break the simplex algorithm.

Would be funny if it came out that all algorithms are P=NP except for vanishignly small subset of cases (which of course is somehow not negligible in practice) and to distinguish them is incomputable :)

Reply on news.ycombinator.com