Will a polynomial time factoring algorithm be found by 2035?
➕
Plus
48
Ṁ2372
2035
9%
chance

Not too much more to say. Resolves Yes if there's an algorithm that can factor big integers before 2035 in polynomial time on a classical computer. Resolves No if it's 2035 and there's still no algorithm.

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

Polynomial dependency on the number itself or on the amount of digits in the number?

@KongoLandwalker I am not the market creator, but I feel confident the intent is the latter, if for no other reason than that there are trivial algorithms achieving the former.

Related market

Can we formalize this, at least a little bit?

To be maximally loop-holey, the algorithm f(n) = {7, 8} gives a set of factors for the set of integers {56} in constant time.

  • Does this algorithm have to be able to factor all big integers?

  • Are we talking about prime factorization, or is giving any product of integers ok?

  • Is this is the worst case runtime?

@DanMan314 Yes. Prime factorization. And yes, that's the definition of polynomial time algorithm I believe.

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