若证明BQP与经典计算机的P等价，Shor算法是否会推翻P≠NP？

已知Shor算法可在量子计算机（属于BQP类）上以多项式时间解决因式分解问题。若证明经典计算机上的BQP与P等价，那么属于NP问题的因式分解是否会成为P≠NP的反例？换句话说，若该结论成立，是否意味着P≠NP不成立，因为我们能在P时间内解决一个NP问题？

核心结论 #

不会直接否定P≠NP的可能性，原因如下：

• 因式分解并非NP完全问题：
  因式分解属于NP类（给定一个候选因数，能在多项式时间内验证它是否整除目标数），但目前学界没有任何证据证明它是NP完全问题。NP完全问题的定义是：所有NP问题都能在多项式时间内归约到该问题。而因式分解不具备这个特性——我们无法把任意NP问题转化为因式分解问题来求解。

• P≠NP的核心是“所有NP问题是否都在P中”：
  P≠NP的断言是“存在至少一个NP问题无法用经典计算机在多项式时间内解决”。反过来，要证明P=NP，必须证明所有NP问题都能被经典P时间算法解决，而不是仅仅某一个NP问题。即便因式分解被证明属于经典P类，也只能说明这一个NP问题能被高效解决，无法推导出所有NP问题都能被高效解决。

• 只有NP完全问题进入P才会直接推出P=NP：
  如果某个NP完全问题被证明属于P，那么根据NP完全性的定义，所有NP问题都能通过多项式归约转化为这个问题，进而在P时间内解决，这才会直接得出P=NP的结论。但因式分解不在这个范畴内。

内容的提问来源于stack exchange，提问作者user15319338