3 ms·
Integer factorization is currently not known to be NP complete, and is expected to not be so. Therefore, even such a breakthrough as posited in the article woul
by shmageggy 13y ago
Integer factorization is currently not known to be NP complete, and is expected to not be so. Therefore, even such a breakthrough as posited in the article would have no immediate bearing on the question of P vs NP.
http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity http://en.wikipedia.org/wiki/Integer_factorization#Difficult...
- yk 13y agoOther way round, multiplication is in P, so integer factorization is in NP. And a breakthrough in P?=NP could have implications for factorization.
- shmageggy 13y ago> so integer factorization is in NP I never said it wasn't. > And a breakthrough in P?=NP could have implications for factorization. Indeed, but what's implied in the article is that they might have made a breakthrough in factorization specifically, not in fundamental CS theory at large.