News for hackers. Stuff that matters.
Re:Quantum Factorization of 143 (2011) by anderskaseorg on Wednesday September 16, 2020 @08:14PM (#24499670)
We have no evidence that factoring is NP-hard, and some evidence that it probably isn’t: the best known classical algorithms for factoring are much faster than those for NP-complete problems. We have no idea whether NP = BQP, or indeed whether either is contained in the other.
Re:Quantum Factorization of 143 (2011) by bollu on Wednesday September 16, 2020 @08:16PM (#24499689)
Yes, which is why I phrased all of this as "hypothetical relations ..."