List of unsolved problems in computer science

This article is a list of notable 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.

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 (SETH) true?
Do one-way functions exist?
- Is public-key cryptography possible?
Log-rank conjecture

Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
Can the discrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
Can the shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
Can the graph isomorphism problem be solved in polynomial time?
Is graph canonization polynomial time equivalent to the graph isomorphism problem?
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]
Can the square-root sum problem be solved in polynomial time in the Turing machine model?

Programming language theory

References

^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete" (PDF), SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936, S2CID 18055798, archived from the original (PDF) on 2019-02-27.
^ 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" (PDF), Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF), Lecture Notes in Computer Science, vol. 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, ISBN 978-3-540-48381-6, MR 2290741.

External links

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.

[1] Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete" (PDF), SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936, S2CID 18055798, archived from the original (PDF) on 2019-02-27.

[2] 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.

[3] Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges" (PDF), Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF), Lecture Notes in Computer Science, vol. 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, ISBN 978-3-540-48381-6, MR 2290741.

[1]

[2]

[3]