3 ms·
Are there examples of problems that were once thought to be NP but later turned out to be P?
by ineedasername 5y ago
Are there examples of problems that were once thought to be NP but later turned out to be P?
- jcranmer 5y agoPrimality testing.
- krasin 5y agoYep, the AKS primality test (2002) was such a surprise to many (including myself) at the time. Most importantly, it did not rely on Riemann hypothesis, which remains unresolved. 1. https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
- CaptainNegative 5y agoTechnically speaking, every problem in P is thought to (and known to) be in both P and NP. You're probably asking about NP-hard problems, where the answer might be no. Primality (which others refer to) was thought to be outside of P, but I'm not sure it was a common conjecture that it was NP hard. The existence of a simple certificate of compositeness places the problem in Co-NP, and so it would have quickly been deduced that Primality is NP-hard only if NP = Co-NP, which I don't think was ever a particularly common conjecture. Pratt found his primality certificate only a couple years after Karp published his famous paper, so I don't expect compositeness was widely thought to be NP-hard, either.
- benibela 5y agoProbably many people thought Majority-3SAT is PP-complete (even harder than NP) But it is in P