Will polynomial NP-complete algorithms be galactic?
Basic
3
Ṁ3110000
62%
chance
1D
1W
1M
ALL
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.
This question is managed and resolved by Manifold.
Get
1,000
and3.00
Related questions
Related questions
Will P vs PSPACE be resolved before P vs NP?
62% chance
Will AI resolve P vs NP by 2050?
27% chance
Can NP-complete problems be solved in polynomial time?
5% chance
Will a polynomial-time algorithm for an NP-complete problem be published by 2030?
4% chance
Will P vs NP be resolved by 2043?
31% chance
Will geometric complexity theory solve P vs NP?
10% chance
Will we be able to solve all NP problems in polynomial time by 2200? (any practical computation method, e.g. BPP, BQP)
2% chance
Will a polynomial time factoring algorithm be found by 2035?
9% chance
Does NP = PSPACE?
6% chance