Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
2 shown
The integer factorization problem: Can the prime factorization of a positive integer be computed in polynomial time? We state the problem by asking if Nat.primeFactorsList is polynomial-time computable (assuming typical encodings of ℕ and List ℕ into bitstrings). Reference: Wikipedia
Strong Sensitivity Conjecture, for every Boolean function f : 0,1^n → 0,1, bs(f) ≤ s(f)^2. We call this the strong sensitivity conjecture because the original sensitivity conjecture only asked for a polynomial bound in terms of s(f).
