News for hackers. Stuff that matters.
Re:The Mathematics Community and the NSA [pdf] by AngrySkillzz on Thursday January 15, 2015 @02:18PM (#8894715)
Good point, thanks. It looks like a few of them, including factorization and the discrete log problem, are conjectured to be NP-intermediate; that is, NP but neither P nor NP complete. However, this class may actually be empty, and is only non-empty if P != NP.

If P = NP, NP-intermediate is necessarily empty, so problems like factorization would be P = NP = NP-complete. You're right, though: the existence of a (classical) polynomial-time factorization algorithm doesn't solve P = NP.

There are no comments on this comment yet.