Resolves YES if by 2200 humanity has the demonstrated capability to solve all NP problems in worst-case polynomial time, with error probability bounded by a constant. Otherwise resolves NO.
If you know about complexity classes: this means P = NP is sufficient but not necessary. BPP = NP (randomized algorithms with constant error probability) would be sufficient, and BQP = NP (quantum algorithms) would also be sufficient if the relevant algorithms could actually be run practically on quantum computers. Other methods could also be sufficient if they meet the resolution criteria.
Any method of computation is allowed for this question, as long as humans can actually do it practically and at reasonable scale. As an example: quantum computers can solve factorization (which is easier than NP-hard) in polytime, but I don't count factorization as solvable in polynomial time today because quantum computers can only do it on toy demonstrations currently.
Because this criteria may be somewhat subjective, the resolution will be based on expert consensus.
1,000
3.00@gregrosent Still counts!
E.g. as stated above, BPP = NP would be sufficient.
The requirement for practical computation method is in reference to the medium of computation, not the practicality of the algorithms. We have practical classical computers, so any polynomial-time classical algorithm, regardless of the constants, will suffice. But we don't have practical quantum computers yet, so quantum algorithms don't count (yet).
Regardless of the actual answer, there's free money at better rates in other markets, so it's worth moving NO shares from this market to those markets:
https://manifold.markets/group/free-money
@Zardoru Yes, I was just giving factorization as an example of a problem I don't count as solvable today. Which is to say, even if it were proved BQP = NP, this market wouldn't resolve YES until practical quantum computers existed.
