Search code examples
npquantum-computing

P vs. NP and Shor's Algorithm


Given that Shor's algorithm can solve factorization in polynomial time on a quantum computer (BQP), if we prove that BQP is the same as P on a classical computer, won't factorization (which is an NP problem) be a counterexample to P != NP?

In other words, if that statement is true, isn't P != NP not true, because we can solve an NP problem (factorization) in P time?


Solution

  • The P vs NP question asks whether every problem in NP is also in P. Therefore, if you just find a single problem in NP that is also in P, that does not itself prove that P = NP. We already know of many problems with this property - since P is a subset of NP, every problem in P is also in NP.

    It is the case that if you can find an NP-complete problem in P then P = NP, but as of now we don’t have a proof that the integer factorization problem (or more properly, the decision version of that problem) is NP-complete.