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 considers it unsolved or when several experts in the field disagree about a solution to a problem.

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

Programming language theory

• POPLmark
• Barendregt–Geuvers–Klop conjecture

Other problems

• Aanderaa–Karp–Rosenberg conjecture
• Generalized star height problem

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
• 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.