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?
[ Parent
| on HN ]
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.