Is Integer Factorization NP-Complete?

This market will resolve once a widely-accepted proof exists that the integer factorization problem is NP-complete or is not NP-complete assuming P != NP.

Sort by:
TassiloNeubauer avatar
Tassilo Neubauer
bought Ṁ80 of NO

I don't get how this market could have a higher market price than this one: Given that integer factorization is in BQP. Giving a reduction of it to an np-complete problem would be equivalent to NP ⊆ BQP if I am not missing something.

ScottLawrence avatar
Scott Lawrence
bought Ṁ188 of NO

@TassiloNeubauer In principle, even if BQP \supseteq NP, that other market could still resolve to NO if it were proven that our universe does not support the construction of a scalable quantum computer.

But no, you're not missing anything, this market was grossly overpriced.