List of unsolved problems in computer science

This article is a list of unsolved problems in computer science. Problems in computer science are 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. This is one of the seven Millennium Prize 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?
• 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?
• Can the discrete logarithm be computed in polynomial time?
• 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
• Generalized star height problem

Other problems

• Aanderaa–Karp–Rosenberg conjecture

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.