P与NP和Shor算法

Question

鉴于Shor算法可以在量子计算机( BQP )上求解多项式时间内的因式分解，如果我们证明BQP和经典计算机上的BQP是相同的，那么分解(这是NP问题)难道不是P != NP的反例吗？

换句话说，如果这个陈述是真的，那么P != NP不是真的吗，因为我们可以在P时间内解决一个NP问题(因式分解)？

Answer 1

prove问题询问NP中的每个问题是否也在P中，因此，如果只在NP中找到一个问题，也就是P中的问题，这本身并不能证明P= NP。我们已经知道许多关于这个性质的问题，因为P是NP的子集，所以P中的每个问题也都是NP中的。

如果你能在P中找到一个NP-完全问题，那么P= NP，但到目前为止，我们还没有证明整数因式分解问题(或者更恰当地说，这个问题的决策版本)是NP-完全的。