4 ms·
Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was comple
by harles 4y ago
Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was completely impractical (I want to say something like N^6). It has an interesting history worth a read - it was also a big USSR contribution to the field, which there weren’t many of at the time.
[0]: https://en.m.wikipedia.org/wiki/Ellipsoid_method https://en.m.wikipedia.org/wiki/Ellipsoid_method
- xref 4y agoOh wow thanks, this is definitely sending me down a Wikipedia rabbit hole; the Ellipsoid method was improved upon via Karmarkar’s algorithm in 1984. Also nicely illustrates that a problem which moves from NP to P can still be moved even further into P-territory _also_ Karmarkar’s algo appears to be an important law case on whether math can be copyrighted for people interested in that angle https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm