3 ms·
But some problems, such as factorization, are known to be solvable on quantum computer in polynomial time, and there is no known program that solves that on det
by stralep 16y ago
But some problems, such as factorization, are known to be solvable on quantum computer in polynomial time, and there is no known program that solves that on det. Turing machine.
I agree that there is no reason to believe that quantum computers will solve NPC problems.
[edit] On det. Turing machine, in polynomial time...
- baddox 16y agoI'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.
- jeffcoat 16y agoIf 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 http://en.wikipedia.org/wiki/Shors_algorithm (Also, remember that factoring is not (known to be) NP-complete.)