Will polynomial NP-complete algorithms be galactic?
4
100Ṁ56
10000
70%
chance

If P=NP is proven, will the polynomial-time algorithms for NP-complete problems (such as SAT) be so complex (i.e., "galactic") that they become impractical for real-world use? "Complex" means extremely large constant factors or exponents.

Upon a formal proof of P=NP, the nature of the discovered algorithms will be evaluated, after which this market will resolve.

Resolves N/A if P ≠ NP.

For example, if the exponential-time algorithm remains faster than the polynomial-time algorithm for typical input sizes, this resolves YES.

Get
Ṁ1,000
to start trading!
Sort by:

Depends on the definition of impractical. Does this only apply at the time the proof is discovered? What if what's practical changes significantly over time?

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