4 ms·

p=np yo

• 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 ago
    Other 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.
• cheald 13y ago
  Prove it.