4 ms·

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 speed

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.