Unsolved Problems
Showing 1-24 of 24 problems
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....
Sums of independent random variables with unbounded variance
Conjecture If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb...
P vs. NP
Problem Is P = NP?...
Exponential Algorithms for Knapsack
Conjecture The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{...
The robustness of the tensor product
Problem Given two codes $R,C$, their Tensor Product $R \otimes C$ is the code that consists of the matrices whose rows are codewords of $R$ and whose ...
Subset-sums equality (pigeonhole version)
Problem Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist dist...
Complexity of square-root sum
Question What is the complexity of the following problem? Given $a_1,\dots,a_n; k$, determine whether or not $\sum_i \sqrt{a_i} \leq k.$...
Linear-size circuits for stable $0,1 < 2$ sorting?
Problem Can $O(n)$-size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$, $f(0x) = 0f(x)$, $f(1x) = 1f...
Discrete Logarithm Problem
If $p$ is prime and $g,h \in {\mathbb Z}_p^*$, we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$. The problem of finding such an int...
P vs. PSPACE
Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, ...
One-way functions exist
Conjecture One-way functions exist....
Unconditional derandomization of Arthur-Merlin games
Problem Prove unconditionally that $\mathcal{AM}$ $\subseteq$ $\Sigma_2$....
P vs. BPP
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a de...
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
Conjecture For every rational $\epsilon > 0$ and every rational $\Delta$, there is no polynomial-time algorithm for the following problem. Given is a...