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.
Computational complexity
*
P versus NP problem
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
* What is the relationship between
BQP
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isaa ...
and
NP?
*
NC = P problem
*
NP = co-NP problem
*
P = BPP problem
*
P = PSPACE problem
*
L = NL problem
*
PH = PSPACE problem
* L = P problem
* L =
RL problem
*
Unique games conjecture
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002.
The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of gam ...
* Is the
exponential time hypothesis true?
** Is the strong exponential time hypothesis (SETH) true?
* Do
one-way functions exist?
** Is
public-key cryptography possible?
*
Log-rank conjecture
Polynomial versus nondeterministic-polynomial time for specific algorithmic problems
* Can
integer factorization be done in
polynomial time on a classical (non-quantum) computer?
* Can the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log'' ...
be computed in polynomial time on a classical (non-quantum) computer?
* Can the
shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
* Can
clustered planar drawings be found in polynomial time?
* Can the
graph isomorphism problem be solved in polynomial time?
* Can
leaf powers and -leaf powers be recognized in polynomial time?
* Can
parity game
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...
s be solved in polynomial time?
* Can the
rotation distance between two
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...
s be computed in polynomial time?
* Can graphs of bounded
clique-width be recognized in polynomial time?
* Can one find a
simple closed quasigeodesic on a convex polyhedron in polynomial time?
* Can a
simultaneous embedding with fixed edges for two given graphs be found in polynomial time?
[.]
Other algorithmic problems
* The
dynamic optimality conjecture: do splay trees have a bounded competitive ratio?
* Is there a -competitive online algorithm for the
-server problem?
* Can a
depth-first search tree be constructed in
NC?
* Can the
fast Fourier transform be computed in time?
* What is the fastest
algorithm for multiplication of two ''n''-digit numbers?
* What is the lowest possible average-case time complexity of
Shellsort
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of ...
with a deterministic, fixed gap sequence?
* Can
3SUM
In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A generalized version, ''k''-SUM, asks the same question on ''k'' numbers. 3SUM can be easily solved in O(n^2) t ...
be solved in strongly sub-quadratic time, that is, in time for some ?
* Can the
edit distance between two strings of length be computed in strongly sub-quadratic time? (This is only possible if the strong
exponential time hypothesis is false.)
* Can
X + Y sorting be done in time?
* What is the
fastest algorithm for matrix multiplication?
* Can
all-pairs shortest paths be computed in strongly sub-cubic time, that is, in time for some ?
* Can the
Schwartz–Zippel lemma for
polynomial identity testing be
derandomized?
* Does
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
admit a
strongly polynomial-time algorithm? (This is problem #9 in
Smale's list of problems.)
* How many queries are required for
envy-free cake-cutting?
* 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.
*
Gilbert–Pollack conjecture on the Steiner ratio of the Euclidean plane
Natural language processing algorithms
* Is there any perfect
syllabification
Syllabification () or syllabication (), also known as hyphenation, is the separation of a word into syllables, whether spoken, written or signed.
Overview
The written separation into syllables is usually marked by a hyphen when using English o ...
algorithm in the English language?
* Is there any perfect
stemming algorithm in the English language?
* Is there any perfect
phrase chunking algorithm in the English language?
* How can computers discern
pronoun ambiguity in the English Language? (Also known as the
Winograd Schema Challenge
The Winograd schema challenge (WSC) is a test of machine intelligence proposed by Hector Levesque, a computer scientist at the University of Toronto. Designed to be an improvement on the Turing test, it is a multiple-choice test that employs quest ...
).
Programming language theory
*
POPLmark
*
Barendregt–Geuvers–Klop conjecture
Other problems
*
Aanderaa–Karp–Rosenberg conjecture
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectures about the number of questions of the form "Is there an ...
*
Černý Conjecture
*
Generalized star-height problem
*
Separating words problem
References
External links
Open problems around exact algorithmsby
Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
The RTA list of open problems– open problems in
rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or redu ...
.
The TLCA List of Open Problems– open problems in area
typed lambda calculus.
{{DEFAULTSORT:Unsolved Problems In Computer Science
Computer Science
Computer Science