4 ms·
primality testing is a poor example. PRIMES is in P. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra
by BrainInAJar 11y ago
primality testing is a poor example. PRIMES is in P.
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
- _asummers 11y agoEven factoring would be a poor example, given that it has never been shown to be NP-complete.
- BrainInAJar 11y agoIt 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.