News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by CaptainNegative on Monday July 19, 2021 @08:50PM (#27888992)
This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
Re:A proof P = NP was accidentally published in TOCT by lovecg on Monday July 19, 2021 @09:40PM (#27889263)
I had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.