List of unsolved problems in computer science
This article is a list of unsolved problems in computer science . Computer science problems are considered unsolved when an expert in the field considers them unsolved or when different experts disagree on a solution to a problem.
Complexity theory
- P-NP problem . This is one of the seven Millennium Problems .
- NC-P problem
- NP-co-NP problem
- P-BPP problem
- P-PSPACE problem
- What is the relationship between BQP and NP ?
- Unique games conjecture
- Is the exponential time hypothesis true?
- Are there one-way functions ?
Algorithms
- What is the fastest algorithm for multiplying two n-digit numbers?
- What is the fastest matrix multiplication algorithm ?
- Can a prime factorization be performed in polynomial time?
- Can the discrete logarithm be calculated in polynomial time?
- Can the graph isomorphism problem be solved in polynomial time?
- Can parity games be solved in polynomial time?
- Does linear programming allow a strictly polynomial time algorithm? This is problem # 9 on Smale's list of problems .
- What is the lower limit of the complexity of a fast Fourier transform algorithm ? Can one be faster than Θ (N log N)?
- Can the 3SUM problem be solved in less than quadratic time complexity ?
- Do splay trees behave optimally dynamically?
- K server problem
Theory of programming languages
Further problems
See also
Web 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.
- 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 .