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.
Computational complexity
- 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?
Algorithms
- 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?
Programming language theory
Other problems
External links
- 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.
| ||||||
This article is issued from Wikipedia - version of the Thursday, February 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.