3 ms·

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?