News for hackers. Stuff that matters.

A comment on An Argument for P=NP (2005) [pdf]. Parent comment

Re:An Argument for P=NP (2005) [pdf] by BrainInAJar on Monday August 17, 2015 @01:40PM (#10074739)
primality testing is a poor example. PRIMES is in P.

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...

[ Parent | on HN ]
Re:An Argument for P=NP (2005) [pdf] by _asummers on Monday August 17, 2015 @01:42PM (#10074758)
Even factoring would be a poor example, given that it has never been shown to be NP-complete.
[ Parent | on HN ]
Re:An Argument for P=NP (2005) [pdf] by BrainInAJar on Monday August 17, 2015 @04:32PM (#10075906)
It would be very surprising if it were, since it's also in co-NP. The other problems in NP intersect co-NP are all in P. It's not at all unlikely, and a lot of evidence points towards, that integer factorization is in P.
[ Parent | on HN ]