Is Integer Factorization NP-Complete?

4%

chance

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:

I don't get how this market could have a higher market price than this one: https://manifold.markets/IsaacKing/can-npcomplete-problems-be-solved-i. 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.

@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.