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 = NP problem
- 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
- K-server problem
- Can X + Y sorting be done in strictly less than O(n2 log n) time?
- Is there a bounded-time algorithm for Envy-free cake-cutting?
- Major unsolved problems in theoretical computer science on StackExchange.
- Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
- Challenges for Theoretical Computer Science (Broken link)
- The Open Problems Project – open problems in computational geometry and related fields.
- The RTA list of open problems – open problems in rewriting.
- The TLCA List of Open Problems – open problems in area typed lambda calculus.