This article is a list of notable unsolved problems in computer science. A problem in computer science is considered unsolved when no solution is known, or when experts in the field disagree about proposed solutions.
What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?
Can 3SUM be solved in strongly sub-quadratic time, that is, in time O(n2−ϵ) for some ϵ>0?
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.)
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.