News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:26PM (#27888008)
Are there examples of problems that were once thought to be NP but later turned out to be P?
Re:A proof P = NP was accidentally published in TOCT by CaptainNegative on Monday July 19, 2021 @08:55PM (#27889021)
Technically 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.

Re:A proof P = NP was accidentally published in TOCT by jcranmer on Monday July 19, 2021 @06:27PM (#27888015)
Primality testing.
Re:A proof P = NP was accidentally published in TOCT by krasin on Monday July 19, 2021 @07:34PM (#27888496)
Yep, 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

Re:A proof P = NP was accidentally published in TOCT by benibela on Tuesday July 20, 2021 @10:13AM (#27893960)
Probably many people thought Majority-3SAT is PP-complete (even harder than NP)

But it is in P