Will polynomial NP-complete algorithms be galactic?
Basic
3
Ṁ31
10000
62%
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
and
S3.00
© Manifold Markets, Inc.Terms + Mana-only TermsPrivacyRules