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 44Computer science 17Physics & astronomy 18Chemistry & materials 13Life sciences 6Earth & society 6
Algorithms 6Complexity 5Computability 2Optimisation 2Machine learning 2
Source Any Curated here 2Optimization constants 1
Verification AnyA · Machine-checkableB · ReproducibleC · Reviewed Tier AnyStandardHardGrand challenges

2 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

Browse by field

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