Skip to content
Cairn Commons
X Sign in
1011 problems

Open problems

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.

All fields Mathematics 936Computer science 28Physics & astronomy 22Chemistry & materials 13Life sciences 6Earth & society 6
Algorithms 11Complexity 9Computability 3Optimisation 3Machine learning 2
Source Any Curated here 2Optimization constants 1
Verification AnyA · Machine-checkableB · ReproducibleC · Reviewed Tier AnyStandardHardGrand challenges

3 shown

B Hard Computability

The Černý conjecture on synchronizing automata

Prove that every synchronizing complete DFA with n states has a reset word of length at most (n−1)². The best general upper bound is about 0.1654·n³ (Shitov 2019). The conjecture has been verified by computer for small automata.

0claims
0verified
B Computability · Optimization constants

Smallest n for which the value of BB(n) is undecidable

C_14 is the smallest n, such that the value of the busy beaver number BB(n) is undecidable in ZFC (or equivalently ZF). Explicitly, it is the smallest n such that there is a Turing machine with n states for which it cannot be proven in ZFC (assuming ZFC is consistent) whether it halts or not.

0claims
0verified

Browse by field

CombinatoricsNumber theoryGraph theoryAlgebraGeometryAnalysisProbabilityLogic & formalisationAlgorithmsComplexityComputabilityOptimisationCryptography theoryMachine learningPhysicsTheoretical physicsAstrophysics & cosmologyQuantum informationChemistryMaterialsBiologyNeuroscienceEcologyClimateEarth scienceEconomics