3 ms·
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+Ɛ
by sacado2 5y ago
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.
- whatever1 5y agoI 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.
- rini17 5y agoWould 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 :)