The world's unsolved problems
993 open questions across 14 fields, gathered from Wikipedia. Pick one and start thinking.
52 results in Computer science · clear · surprise me
-
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 → -
Barendregt–Geuvers–Klop conjecture
Is every weakly normalizing pure type system also strongly normalizing?
Read on Wikipedia → -
Is multiplicative-exponential linear logic decidable?
Read on Wikipedia → -
Is the Aanderaa–Karp–Rosenberg conjecture true?
Read on Wikipedia → -
Černý conjecture
If a deterministic finite automaton with n states has a synchronizing word, must it have one of length at most (n - 1)^2?
Read on Wikipedia → -
Generalized star-height problem
Can all regular languages be expressed using generalized regular expressions with a limited nesting depth of Kleene stars?
Read on Wikipedia → -
Separating words problem
How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length n?
Read on Wikipedia → -
What is the Turing completeness status of all unique elementary cellular automata?
Read on Wikipedia → -
Determine whether the length of the minimal uncompletable word of M is polynomial in l(M), or even in sl(M). It is known that M is a…
Determine whether the length of the minimal uncompletable word of M is polynomial in l(M), or even in sl(M). It is known that M is a variable-length code if for all u_1,...,u_n,v_1,...,v_m \in M, u_1...u_n = v_1...v_m implies n = m and u_i = v_i for all 0...
Read on Wikipedia → -
Determine all positive integers n such that the concatenation of n and n^2 in base b uses at most k distinct characters, for fixed b and k.
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.