Posts
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 considers it unsolved or when several experts in the field
disagree about a solution to a problem.
Stay Connected... Follow Post.
Stay Connected... Follow Post.
Contents
Computational complexity theory
- P = NP problem
- NC = P problem
- NP = co-NP problem
- P = BPP problem
- P = PSPACE problem
- L = NL problem
- What is the relationship between BQP and NP?
- Unique games conjecture
- Is the exponential time hypothesis true?
- Do one-way functions exist?
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?
- 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)?
- Can the 3SUM problem be solved in subquadratic time?
- Dynamic optimality conjecture for splay trees
- K-server problem
No comments:
Post a Comment