News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.