List of unsolved problems in computer science

Computational complexity

• P versus NP problem
• What is the relationship between BQP and NP?
• NC = P problem
• NP = co-NP problem
• P = BPP problem
• P = PSPACE problem
• L = NL problem
• PH = PSPACE problem
• L = P problem
• L = RL problem
• Unique games conjecture
• Is the exponential time hypothesis true?
• * Is the strong exponential time hypothesis true?
• Do one-way functions exist?
• * Is public-key cryptography possible?
• Log-rank conjecture

  Polynomial versus non-polynomial time for specific algorithmic problems

• Can integer factorization be done in polynomial time on a classical computer?
• Can the discrete logarithm be computed in polynomial time?
• Can the shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
• Can clustered planar drawings be found in polynomial time?
• Can the graph isomorphism problem be solved in polynomial time?
• Can leaf powers and -leaf powers be recognized in polynomial time?
• Can parity games be solved in polynomial time?
• Can the rotation distance between two binary trees be computed in polynomial time?
• Can graphs of bounded clique-width be recognized in polynomial time?
• Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?
• Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?

  Other algorithmic problems

• The dynamic optimality conjecture: do splay trees have a bounded competitive ratio?
• Is there a -competitive online algorithm for the -server problem?
• Can a depth-first search tree be constructed in NC?
• Can the fast Fourier transform be computed in time?
• What is the fastest algorithm for multiplication of two n-digit numbers?
• What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?
• Can 3SUM be solved in strongly sub-quadratic time, that is, in time for some ?
• Can the edit distance between two strings of length be computed in strongly sub-quadratic time?
• Can X + Y sorting be done in time?
• What is the fastest algorithm for matrix multiplication?
• Can all-pairs shortest paths be computed in strongly sub-cubic time, that is, in time for some ?
• Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
• Does linear programming admit a strongly polynomial-time algorithm?
• How many queries are required for envy-free cake-cutting?
• What is the algorithm for the lookup table that consistently generates playable mazes in the 1982 Atari 2600 game Entombed merely from the values of the five pixels adjacent to the next ones to be generated?

  Natural language processing algorithms

• Is there any perfect syllabification algorithm in the English language?
• Is there any perfect stemming algorithm in the English language?
• Is there any perfect POS tagging algorithm in the English language?
• How can computers discern pronoun ambiguity in the English Language?.

  Programming language theory

• POPLmark
• Barendregt–Geuvers–Klop conjecture

  Other problems

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