Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I'm not familiar with this quantum algorithm for factorization, or the "standard" factorization algorithm. Are we talking about integer factorization? It doesn't seem obvious to me how factorization would even be phrased as a decision problem. I know that primality testing is known to be in P.

I don't know if any of this comment even makes since, considering I believe the complexity classes P and NP are formally defined in terms of Turing machines anyway. Any NPC problem along with some polynomial computation can be used to solve any other NPC problem. I don't think quantum computers aren't going to reveal a polynomial-time algorithm for a known NPC problem.



If someone refers to the "standard" algorithm for factoring on quantum computers, they're talking about Shor's algorithm.

http://en.wikipedia.org/wiki/Shors_algorithm

(Also, remember that factoring is not (known to be) NP-complete.)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: