List of unsolved problems in computer science
This article is a list of unsolved problems in computer science. A problem in computer science is considered unsolved when an expert in the field (i.e, a computer scientist) considers it unsolved or when several experts in the field disagree about a solution to a problem.
- P versus NP problem (often written as "P = NP," which is technically not correct for the problem or those below)
- NC = P problem
- NP = co-NP problem
- P = BPP problem
- P = PSPACE problem
- L = NL problem
- L = P problem
- L = RL problem
- What is the relationship between BQP and NP?
- Unique games conjecture
- Is the exponential time hypothesis true?
- Do one-way functions exist?
- Is public-key cryptography possible?
- What is the fastest algorithm for multiplication of two n-digit numbers?
- What is the fastest algorithm for matrix multiplication?
- Can integer factorization be done in polynomial time on a classical computer?
- Can the discrete logarithm be computed in polynomial time on a classical computer?
- Can the graph isomorphism problem be solved in polynomial time?
- Can parity games be solved in polynomial time?
- Can the rotation distance between two binary trees be computed in polynomial time?
- Does linear programming admit a strongly polynomial-time algorithm? This is problem #9 in Smale's list of problems.
- What is the lower bound on the complexity of fast Fourier transform algorithms? Can they be faster than Θ (N log N)?
- Dynamic optimality conjecture for splay trees
- Can we compute the edit distance between two strings of length n in strongly sub-quadratic time, i.e., in time O(n2−ϵ) for some ϵ>0 ?
- K-server problem
- Can X + Y sorting be done in strictly less than O(n2 log n) time?
- How many queries are required for envy-free cake-cutting?
- Aanderaa–Karp–Rosenberg conjecture
- Generalized star height problem
- Separating words problem
- Possibility of hypercomputation