OP-0035Algorithms and data structuresOpen
Beating 2^n for the travelling salesman problem
Held–Karp has stood since 1962. No exact algorithm is known with running time O(1.99^n).
Community consensus· 1962
The index
Algorithms and data structures
5 entries matching the current filters. Sorted by recently added.
OP-0034Algorithms and data structuresOpen
Is graph isomorphism in P?
Babai's quasipolynomial algorithm moved the problem, but the gap to polynomial time remains.
Community consensus· 1972
OP-0032Algorithms and data structuresOpen
The 3SUM conjecture
Is there any truly subquadratic algorithm for finding three numbers summing to zero?
Community consensus· 1995
OP-0031Algorithms and data structuresOpen
The dynamic optimality conjecture
Are splay trees within a constant factor of the best possible binary search tree, on every access sequence?
Community consensus· 1985
OP-0028Algorithms and data structuresOpen
Is the exponent of matrix multiplication equal to 2?
Every improvement since 1969 has shaved digits off 2.37. Nobody can rule out 2 + o(1), and nobody can achieve it.
Community consensus· 1969
Frequent tags
theoremdb 3909historical workshop 3469aim 3469icm 2898source curated 2675source candidate 1231number theory 1007status unassessed 622specialist collection 522pde dyn 399geometry 336analysis 269algebraic geometry 257algebra 224verifiable 2026 223probability 221graph theory 200topology 199lie rep 180combinatorics 154combinatorics discrete mathematics 141mathematical physics mechanics 137numerical analysis computer science 131research 2026 126