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.
