Unsolved Problems
Showing 1-11 of 11 problems
Category
Problem Set
Status
P versus NP Problem
Does $P = NP$? More formally: if the solution to a problem can be quickly verified (in polynomial time), can the solution also be quickly found (in po...
The Unique Games Conjecture
For certain constraint satisfaction problems (unique games), it is NP-hard to approximate the maximum fraction of satisfiable constraints beyond a cer...
The Polynomial Hirsch Conjecture
The diameter of the graph of a $d$-dimensional polytope with $n$ facets is bounded by a polynomial in $d$ and $n$....
Smale's 4th Problem: Integer Zeros of Polynomials
Find efficient algorithms for deciding whether a polynomial with integer coefficients has an integer root....
Smale's 9th Problem: Linear Programming in Polynomial Time
Find a strongly polynomial algorithm for linear programming....
Beyond Convex Optimization
Determine whether algebraic geometry can systematically replace linear algebra in optimization....
Mathematics of Quantum Computing
Develop the mathematics required to control the quantum world for computation....
Game Theory at Scale
Create scalable mathematics for differential games, replacing traditional PDE approaches....
Computation at Scale
Develop asymptotics for systems with massive degrees of freedom....
Computational Duality
Use mathematical duality and geometry as foundations for developing novel computational algorithms....
Occam's Razor in Many Dimensions
Find lower bounds for sensing complexity as data collection grows, addressing entropy maximization....