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.
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.