3 ms·
> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain Wish they’d given/linked a few examples there, anyone
by xref 4y ago
> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain
Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?
- harles 4y agoNot 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
- JohnKemeny 4y agoPRIMES, checking whether a number is a prime number or not. It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.
- adgjlsfhk1 4y agoPrimes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.