The world's unsolved problems
993 open questions across 14 fields, gathered from Wikipedia. Pick one and start thinking.
Showing all 993 problems · surprise me
-
Log-rank conjecture
Read on Wikipedia → -
Hartmanis–Stearns conjecture
Read on Wikipedia → -
Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
Read on Wikipedia → -
Can the discrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
Read on Wikipedia → -
Can the shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
Read on Wikipedia → -
Can the graph isomorphism problem be solved in polynomial time on a classical computer?
Read on Wikipedia → -
Is graph canonization polynomial-time equivalent to the graph isomorphism problem?
Read on Wikipedia → -
Can leaf powers and k-leaf powers be recognized in polynomial time?
Read on Wikipedia → -
Can parity games be solved in polynomial time?
Read on Wikipedia → -
Can graphs of bounded clique-width be recognized in polynomial time?
Read on Wikipedia → -
Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?
Read on Wikipedia → -
Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?
Read on Wikipedia → -
Can the square-root sum problem be solved in polynomial time in the Turing machine model?
Read on Wikipedia → -
Skolem problem
Is it decidable whether an algebraic linear recurrence sequence has a zero?
Read on Wikipedia → -
Hilbert's tenth problem over the field of rational numbers
Read on Wikipedia → -
The dynamic optimality conjecture
Do splay trees have a bounded competitive ratio?
Read on Wikipedia → -
Can a depth-first search tree be constructed in NC?
Read on Wikipedia → -
Can the fast Fourier transform be computed in o(n log n) time?
Read on Wikipedia → -
What is the fastest algorithm for multiplication of two n-digit numbers?
Read on Wikipedia → -
What is the lowest possible average-case time complexity of Shellsort with a deterministic fixed gap sequence?
Read on Wikipedia → -
Can 3SUM be solved in strongly sub-quadratic time, that is, in time O(n2−ϵ) for some ϵ > 0?
Read on Wikipedia → -
Can the edit distance between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong…
Can the edit distance between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.)
Read on Wikipedia → -
Can X + Y sorting be done in o(n2 log n) time?
Read on Wikipedia → -
What is the fastest algorithm for matrix multiplication?
Read on Wikipedia → -
Can all-pairs shortest paths be computed in strongly sub-cubic time, that is, in time O(V3−ϵ) for some ϵ > 0?
Read on Wikipedia → -
Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
Read on Wikipedia → -
Does linear programming admit a strongly-polynomial time algorithm? (This is problem #9 in Smale's list of problems.)
Read on Wikipedia → -
How many queries are required for envy-free cake-cutting?
Read on Wikipedia → -
What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST…
What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST problem? The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown.
Read on Wikipedia → -
Gilbert–Pollak conjecture
Is the Steiner ratio of the Euclidean plane equal to 2/\sqrt{3}?
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.