4 ms·

"This proves the polynomial time bound."

• ncann 6y ago
  I would be very skeptical if there is indeed a poly time algorithm for integer factorization. If that's actually what the paper claims then it's a very big claim.
• dleslie 6y ago
  If true... Hot damn! There's NP-Hard problems that if we had polynomial time solutions for we could vastly improve the quality of life on earth.
  • gnulinux 6y ago
    Integer factorizatiom not proved to be NP-complete. It's been guessed to be "hard" for a while.
  • LeegleechN 6y ago
    Integer factoring is in a fairly sparse in-between zone between polynomial and NP Hard problems. This is why quantum computers can have a near exponential speedup from them (disregarding this claimed result) and only a polynomial speedup for NP Hard problems. So even if this result holds it can't be converted into a fast solution for all NP Hard problems.
    • dleslie 6y ago
      Ah, bummer. For some reason I thought it was NP-hard; thank-you for the correction.
    • hedora 6y ago
      Though, if conventional computers can factor in polynomial time after all, I wonder if that would suggest quantum computing is no better than a polynomial speedup.
  • sudosysgen 6y ago
    Which ones?