Will we be able to solve all NP problems in polynomial time by 2200? (any practical computation method, e.g. BPP, BQP)
➕
Plus
12
Ṁ892
2201
1.7%
chance

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.

Get
Ṁ1,000
and
S3.00
Sort by:

What’s your policy on polynomial-time algorithms that are practically infeasible because the constants are large?

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

I'd suggest adding the relevant complexity classes to the title. As is, I feel it's slightly misleading.

predicts NO

@jskf Good suggestion, was hard to fit it into the character limit but hope that helps.

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

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

predicts NO

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

Inspired by discussion in this market:

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

© Manifold Markets, Inc.Terms + Mana-only TermsPrivacyRules