# List of unsolved problems in computer science

Jump to navigation
Jump to search

This article is a list of unsolved problems in computer science. A problem in computer science is considered unsolved when no solution is known, or when experts in the field disagree about proposed solutions.

## Contents

## Computational complexity[edit]

- P versus NP problem (occasionally written erroneously as "P = NP")
- 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 (SETH) true?

- Do one-way functions exist?
- Is public-key cryptography possible?

## Polynomial versus non-polynomial time for specific algorithmic problems[edit]

- Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
- Can integer factorization be considered to be NP-complete?
- Can clustered planar drawings be found in polynomial time?
- Can the discrete logarithm be computed in polynomial time?
- Can the graph isomorphism problem be solved in polynomial time?
- Can leaf powers and k-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?
^{[1]} - Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?
^{[2]} - Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?
^{[3]}

## Other algorithmic problems[edit]

- What is the fastest algorithm for multiplication of two
*n*-digit numbers? - What is the fastest algorithm for matrix multiplication?
- Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
- Can a depth-first search tree be constructed in NC?
- 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
*o*(*N*log*N*)? - The dynamic optimality conjecture: do splay trees have a bounded competitive ratio?
- Can we compute the edit distance between two strings of length
*n*in strongly sub-quadratic time, i.e., in time*O*(*n*^{2−ϵ}) for some ϵ>0 ? - Is there a k-competitive online algorithm for the k-server problem?
- Can X + Y sorting be done in better than
*o*(*n*^{2}log*n*) time? - How many queries are required for envy-free cake-cutting?
- What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?

## Natural Language Processing algorithms[edit]

- 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?

## Programming language theory[edit]

## Other problems[edit]

- Aanderaa–Karp–Rosenberg conjecture
- Generalized star height problem
- Separating words problem
- Possibility of hypercomputation

## References[edit]

**^**Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete",*SIAM Journal on Discrete Mathematics*,**23**(2): 909–939, doi:10.1137/070687256, MR 2519936.**^**Demaine, Erik D.; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik–Schnirelmann",*Geometric folding algorithms: Linkages, origami, polyhedra*, Cambridge: Cambridge University Press, pp. 372–375, doi:10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, MR 2354878.**^**Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges",*Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers*, Lecture Notes in Computer Science,**4271**, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, MR 2290741.

## External links[edit]

- Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
- The RTA list of open problems – open problems in rewriting.
- The TLCA List of Open Problems – open problems in area typed lambda calculus.