Computational complexity
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
153 records · Search and filter
- Math-1174 Linear-size circuits for stable $0,1 < 2$ sorting?
- Math-1176 Unconditional derandomization of Arthur-Merlin games
- Math-2067 10 Lectures and 42 Open Problems — Hardness at the Cheeger square-root gap
- Math-2317 Arithmetic-Formula Lower Bounds for Permanent and Determinant
- Math-2352 Unique Games Approximation-Threshold Conjecture
- Math-2448 $d$-to-$1$ Games Conjecture
- Math-2971 Constant-factor hardness of directed feedback vertex set
- Math-2973 Counting-hierarchy upper bound for existential-universal real sentences
- Math-2974 Explicit super-square-root-exponential depth-three circuits
- Math-2976 Unconditional time lower bounds for fixed-dimensional WL
- Math-2979 Depth-five homogeneous lower bounds for iterated matrix multiplication
- Math-2981 Exponential semidefinite complexity for perfect matching
- Math-2982 Optimal Max-Cut approximation hardness
- Math-2986 Constant-factor hardness of Min-UnCut
- Math-2992 Perfect-completeness two-to-one hardness
- Math-2994 Cubic border-determinantal lower bound for the permanent
- Math-2996 Average sensitivity of polynomial threshold functions
- Math-2998 Quasilinear robust PCP for PPAD
- Math-3002 Quadratic sensitivity versus block sensitivity
- Math-3006 Independent-set hardness with a three-colorability promise
- Math-3011 Constant-factor hardness of uniform sparsest cut
- Math-3013 EXPTIME-completeness of variable-dimensional WL
- Math-3014 Factor-two hardness of Vertex Cover
- Math-3016 Complexity of Weisfeiler–Leman graph identification
- Math-4184 Hartmanis–Stearns conjecture
- Math-4378 10 Lectures and 42 Open Problems — Consistency and sample complexity of Multireference Alignment
- Math-4404 Markov-basis complexity depends on representation
- Math-4456 Approximability and Parameterized Complexity of Steiner Forest
- Math-4457 Hardness of the $\varepsilon-Dense$ Steiner Tree Problem
- Math-4458 Complexity and Approximation of Planar Min-Bisection
- Math-4464 Polynomial Complexity of Greedy Lattice Reduction
- Math-4468 Computational Hardness of Learning Parity with Noise
- Math-4469 Quantum Hardness of Approximate Lattice Problems
- Math-4470 Three-Terminal Distance-Interdiction Complexity
- Math-4476 Complexity of Dense Perfect Hypergraph Matching
- Math-4477 Separation of Constant-Free Valiant Classes
- Math-4478 Optimal Algebraic Immunity of Boolean Functions
- Math-4486 Rotational Matching Complexity for Planar Point Sets
- Math-4495 Sensitivity Growth Under Boolean Conjunctions
- Math-4496 Orbit-Closure Obstructions for Permanent–Determinant Separation
- Math-4505 Worst-Case Inputs for Smoothed Caching Complexity
- Math-4512 Complexity of Maximizing Initial Odd Ears
- Math-4517 Complexity of Embedding Two-Complexes in Three-Manifolds
- Math-4518 Complexity and Rank of Completely Positive Matrices
- Math-4523 Randomized Communication Complexity of Distributed Triangle Detection
- Math-4524 Overlap Gaps and Algorithmic Hardness of Submatrix Detection
- Math-4526 Complexity of Bray’s Involution-Centralizer Algorithm
- Math-4531 Round Complexity of Non-Malleable Commitments
- Math-4532 Average-Case Hardness of Quasi-Cyclic Code Problems
- Math-4533 Sampling Complexity of Hyperbolic-Cross Approximation