List of open problems in computer science

This article is a list of unsolved problems in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

. Problems in computer science are considered unsolved when an expert in the field considers it unsolved or when several experts in the field disagree about a solution to a problem.

P = NP problem. This is one of the seven Millennium Prize Problems
Millennium Prize Problems
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. As of September 2011, six of the problems remain unsolved. A correct solution to any of the problems results in a US$1,000,000 prize being awarded by the institute...

.
NC = P problem
NP = co-NP problem
P = BPP problem
P = PSPACE problem
What is the relationship between BQP
BQP
In computational complexity theory 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...

and NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

?
Unique games conjecture
Unique games conjecture
In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...
Is the exponential time hypothesis
Exponential time hypothesis
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption formalized by stating that 3-SAT cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP...

true?
Do one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...

s exist?

What is the fastest algorithm for multiplication of two n-digit numbers?
What is the fastest algorithm for matrix multiplication?
Can integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

be done in polynomial time?
Can the discrete logarithm be computed in polynomial time?
Can the graph isomorphism problem
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...

be solved in polynomial time?
Can parity game
Parity game
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of finitely many natural numbers. Two players, 0 and 1, take turns moving a token along the edges of the graph, resulting in a path, called the play.The winner of a finite play is the...

s be solved in polynomial time?
Does linear programming admit a strongly polynomial-time algorithm? This is problem #9 in Smale's list
Smale's problems
Smale's problems refers to a list of eighteen unsolved problems in mathematics that was proposed by Steve Smale in 2000. Smale composed this list in reply to a request from Vladimir Arnold, then president of the International Mathematical Union, who asked several mathematicians to propose a list of...

of problems.
What is the lower bound on the complexity of fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...

algorithms? Can they be faster than Θ(N log N)?
Can the 3SUM
3SUM
In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:There is a simple algorithm to solve 3SUM in O time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds...

problem be solved in subquadratic time?
Dynamic optimality conjecture for splay trees
K-server problem
K-server problem
The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis...

POPLmark
Barendregt–Geuvers–Klop conjecture
Generalized star height problem
Generalized star height problem
The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they...

Major unsolved problems in theoretical computer science on StackExchange.
Open problems around exact algorithms by Gerhard J.