Will we be able to solve all NP problems in polynomial time by 2200?

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. Because this criteria may be somewhat subjective, the resolution will be based on expert consensus.

Any method of computation is allowed for this question, as long as humans can actually do it practically and at reasonable scale. E.g. quantum computers can solve factorization 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.

Sort by:
Zardoru avatar
bought Ṁ1 of NO

Factorization is not NP-Complete.

Quantum computers are not expected to be able solve NP-problems in polynomial time. ("NP is not contained in BQP" is not proved but strongly conjectured.)

jack avatar
is predicting NO at 2%

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

jack avatar
bought Ṁ300 of NO

Inspired by discussion in this market:

ManifoldDream avatar

Will we be able to solve all NP problems in polynomial time by 2200?, 8k, beautiful, illustration, trending on art station, picture of the day, epic composition