This article is a list of 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 (occasionally written erroneously as "P = NP")
- What is the relationship between BQP and NP?
- NC = P problem
- NP = co-NP problem
- P = BPP problem
- P = PSPACE problem
- L = NL problem
- L = P problem
- L = RL problem
- Unique games conjecture
- Is the exponential time hypothesis true?
- Do one-way functions exist?
- Is public-key cryptography possible?
Polynomial versus non-polynomial time for specific algorithmic problems
- Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
- Is integer factorization NP-complete?
- Can clustered planar drawings be found in polynomial time?
- Can the discrete logarithm be computed in polynomial time?
- Can the graph isomorphism problem be solved in polynomial time?
- Can leaf powers and k-leaf powers be recognized in polynomial time?
- Can parity games be solved in polynomial time?
- Can the rotation distance between two binary trees 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
- What is the fastest algorithm for multiplication of two n-digit numbers?
- What is the fastest algorithm for matrix multiplication?
- Can the Schwartzâ€"Zippel lemma for polynomial identity testing be derandomized?
- Can a depth-first search tree be constructed in NC?
- 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 O(N log N)?
- The dynamic optimality conjecture: do splay trees have a bounded competitive ratio?
- 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 ?
- Is there a k-competitive online algorithm for the 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?
- What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?
Programming language theory
- POPLmark
- Barendregtâ€"Geuversâ€"Klop conjecture
Other problems
- Aanderaaâ€"Karpâ€"Rosenberg conjecture
- Generalized star height problem
- Separating words problem
- Possibility of hypercomputation
References
External links
- Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397â€"405.
- The RTA list of open problems â€" open problems in rewriting.
- The TLCA List of Open Problems â€" open problems in area typed lambda calculus.
