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
Find better polynomial-time approximation algorithms for the metric Traveling Salesman Problem and prove the conjectured 4/3 integrality gap of the subtour LP. The best known ratio is 3/2 − ε with ε > 10^−36 (Karlin–Klein–Oveis Gharan).
Determine ω, the smallest exponent such that n×n matrices can be multiplied with n^(ω+o(1)) arithmetic operations. The best published bound is ω < 2.371339, a 2026 preprint claims ω < 2.371177, and it is conjectured that ω = 2.
