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.
1,000
3.00@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.
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.