Will a polynomial time factoring algorithm be found by 2035?

1.4kṀ2572

2035

chance

ALL

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.

Computational Complexity Theory

Get

1,000

to start trading!

People are also trading

Will the prime factors of RSA-1024 be known by 2030?

21% chance

Will the prime factors of RSA-2048 be known before 2030?

13% chance

Will a polynomial-time algorithm for an NP-complete problem be published by 2030?

4% chance

Can integer factorization be solved in polynomial time on a classical computer?

10% chance

Will a quantum computer factor the RSA-2048 challenge number before 2035?

47% chance

Will a quantum computer factor the RSA-2048 challenge number before 2030?

8% chance

Will a quantum computer factor the RSA-2048 challenge number before 2050?

81% chance

Will a quantum computer factor the RSA-2048 challenge number before 2075?

78% chance

Will a quantum computer factor the RSA-2048 challenge number before 2045?

66% chance

In what year will the 1801st Fibonacci number be fully factorized?

5 Comments

46 Holders

82 Trades

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?