Hacker News Reader

Comment by xref | Hacker News Reader

> 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?

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

Oh 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

PRIMES, 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.

Primes 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.

Reply on news.ycombinator.com