List of unsolved problems in computer science

{{Main article|Computational complexity theory}}

• P versus NP problem - The P vs NP problem is a major unsolved question in computer science that asks whether every problem whose solution can be quickly verified by a computer (NP) can also be quickly solved by a computer (P). This question has profound implications for fields such as cryptography, algorithm design, and computational theory.{{Cite web |date=2023-12-01 |title=P vs. NP – The Greatest Unsolved Problem in Computer Science |url=https://www.quantamagazine.org/videos/p-vs-np-the-greatest-unsolved-problem-in-computer-science/ |access-date=2025-03-11 |website=Quanta Magazine |language=en}}
• 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

{{Main article|NP-intermediate}}

• 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 on a classical computer?

The graph isomorphism problem involves determining whether two finite graphs are isomorphic, meaning there is a one-to-one correspondence between their vertices and edges that preserves adjacency. While the problem is known to be in NP, it is not known whether it is NP-complete or solvable in polynomial time. This uncertainty places it in a unique complexity class, making it a significant open problem in computer science.{{Cite web |last=Klarreich |first=Erica |date=2015-12-14 |title=Landmark Algorithm Breaks 30-Year Impasse |url=https://www.quantamagazine.org/algorithm-solves-graph-isomorphism-in-record-time-20151214/ |access-date=2025-03-11 |website=Quanta Magazine |language=en}}

• Is graph canonization polynomial time equivalent to the graph isomorphism problem?
• Can leaf powers and {{mvar|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?{{Cite journal |last1=Fellows |first1=Michael R. |author-link1=Michael Fellows |last2=Rosamond |first2=Frances A. |author-link2=Frances A. Rosamond |last3=Rotics |first3=Udi |last4=Szeider |first4=Stefan |author-link4=Stefan Szeider |year=2009 |title=Clique-width is NP-complete |url=http://pdfs.semanticscholar.org/92fb/456bfe2f1f9f7f7445a1c24f0ee53b7e264b.pdf |url-status=dead |journal=SIAM Journal on Discrete Mathematics |volume=23 |issue=2 |pages=909–939 |doi=10.1137/070687256 |mr=2519936 |s2cid=18055798 |archive-url=https://web.archive.org/web/20190227163512/http://pdfs.semanticscholar.org/92fb/456bfe2f1f9f7f7445a1c24f0ee53b7e264b.pdf |archive-date=2019-02-27}}
• Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?{{Cite book |last1=Demaine |first1=Erik D. |author-link1=Erik Demaine |title=Geometric folding algorithms: Linkages, origami, polyhedra |title-link=Geometric Folding Algorithms |last2=O'Rourke |first2=Joseph |author-link2=Joseph O'Rourke (professor) |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-71522-5 |location=Cambridge |pages=372–375 |chapter=24 Geodesics: Lyusternik–Schnirelmann |doi=10.1017/CBO9780511735172 |mr=2354878}}
• Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?{{Cite book |last1=Gassner |first1=Elisabeth |url=http://e-archive.informatik.uni-koeln.de/507/2/zaik2006-507.pdf |title=Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22–24, 2006, Revised Papers |last2=Jünger |first2=Michael |last3=Percan |first3=Merijam |last4=Schaefer |first4=Marcus |last5=Schulz |first5=Michael |publisher=Springer |year=2006 |isbn=978-3-540-48381-6 |series=Lecture Notes in Computer Science |volume=4271 |location=Berlin |pages=325–335 |chapter=Simultaneous graph embeddings with fixed edges |doi=10.1007/11917496_29 |mr=2290741 |chapter-url=http://e-archive.informatik.uni-koeln.de/507/2/zaik2006-507.pdf}}.
• Can the square-root sum problem be solved in polynomial time in the Turing machine model?

• The dynamic optimality conjecture: Do splay trees have a bounded competitive ratio?
• Can a depth-first search tree be constructed in NC?
• Can the fast Fourier transform be computed in {{math|o(n log n)}} 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 {{math|O(n^2−ϵ)}} for some {{math|ϵ>0}}?
• Can the edit distance between two strings of length {{math|n}} be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.)
• Can X + Y sorting be done in {{math|o(n² log n)}} 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 {{math|O(V^3−ϵ)}} for some {{math|ϵ>0}}?
• Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
• Does linear programming admit a strongly polynomial-time algorithm? (This is problem #9 in Smale's list of problems.)
• How many queries are required for envy-free cake-cutting?
• What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST problem? The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown.
• Gilbert–Pollak conjecture: Is the Steiner ratio of the Euclidean plane equal to $2/\backslash sqrt\; 3$?

{{Main article|Programming language theory}}

• Barendregt–Geuvers–Klop conjecture

• Is the Aanderaa–Karp–Rosenberg conjecture true?
• Černý Conjecture: If a deterministic finite automaton with $n$ states has a synchronizing word, must it have one of length at most $(n-1)^2$?
• Generalized star-height problem: Can all regular languages be expressed using generalized regular expressions with a limited nesting depth of Kleene stars?
• Separating words problem: How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length $n$?
• What is the Turing completeness status of all unique elementary cellular automata?
• The problem (still open as of 2018) to determine whether the length of the minimal uncompletable word of $M$ is polynomial in $l(M)$, nor even whether it's polynomial in $sl(M)$. It's said that $M$ is a variable-length code for all $u\_1,...,u\_n,v\_1,...,v\_m\; \backslash in\; M$, if $u\_1...u\_n=v\_1...v\_m$ then $n=m$ and for all
• The problem to determine all positive integers $n$ such that the concatenation of $n$ and $n^2$ in base $b$ uses at most $k$ distinct characters for $b$ and $k$ fixed{{cn|date=September 2024}} and many other problems in the coding theory are also the unsolved problems in mathematics.

{{reflist}}

• [https://www.sciencedirect.com/science/article/pii/S0166218X0700128X Open problems around exact algorithms] by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
• [http://www.cs.tau.ac.il/~nachum/rtaloop/ The RTA list of open problems] – open problems in rewriting.
• [http://tlca.di.unito.it/opltlca/ The TLCA List of Open Problems] – open problems in area typed lambda calculus.

{{unsolved problems}}

{{DEFAULTSORT:Unsolved Problems In Computer Science}}

Computer Science

Computer Science