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

• 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.^[1]
• What is the relationship betweenBQP andNP?
• 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 theexponential time hypothesis true?
  • Is the strong exponential time hypothesis (SETH) true?
• Doone-way functions exist?
  • Ispublic-key cryptography possible?
• Log-rank conjecture
• Hartmanis–Stearns conjecture

• Caninteger factorization be done inpolynomial time on a classical (non-quantum) computer?
• Can thediscrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
• Can theshortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
• Can thegraph 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.^[2]

• Isgraph canonization polynomial-time equivalent to the graph isomorphism problem?
• Canleaf powers andk-leaf powers be recognized in polynomial time?
• Canparity games be solved in polynomial time?
• Can therotation distance between twobinary trees be computed in polynomial time?
• Can graphs of boundedclique-width be recognized in polynomial time?^[3]
• Can one find asimple closed quasigeodesic on a convex polyhedron in polynomial time?^[4]
• Can asimultaneous embedding with fixed edges for two given graphs be found in polynomial time?^[5]
• Can thesquare-root sum problem be solved in polynomial time in the Turing machine model?

• Skolem problem: Is it decidable whether an algebraic linear recurrence sequence has a zero?
• Hilbert's tenth problem over the field of rational numbers

• Thedynamic optimality conjecture: Do splay trees have a bounded competitive ratio?
• Can adepth-first search tree be constructed inNC?
• Can thefast Fourier transform be computed ino(n logn) time?
• What is the fastestalgorithm for multiplication of twon-digit numbers?
• What is the lowest possible average-case time complexity ofShellsort with a deterministic fixed gap sequence?
• Can3SUM be solved in strongly sub-quadratic time, that is, in timeO(n^2−ϵ) for someϵ > 0?
• Can theedit distance between two strings of lengthn be computed in strongly sub-quadratic time? (This is only possible if the strongexponential time hypothesis is false.)
• CanX + Y sorting be done ino(n² logn) time?
• What is thefastest algorithm for matrix multiplication?
• Canall-pairs shortest paths be computed in strongly sub-cubic time, that is, in timeO(V^3−ϵ) for someϵ > 0?
• Can theSchwartz–Zippel lemma forpolynomial identity testing bederandomized?
• Doeslinear programming admit astrongly polynomial-time algorithm? (This is problem #9 inSmale's list of problems.)
• How many queries are required forenvy-free cake-cutting?
• What is the algorithmic complexity of theminimum spanning tree problem? Equivalently, what is thedecision tree complexity of the MST problem? The optimal algorithm to compute MSTs isknown, but it relies on decision trees, so its complexity is unknown.
• Gilbert–Pollak conjecture: Is theSteiner ratio of theEuclidean plane equal to${\displaystyle 2/\sqrt{3}}$?

• Barendregt–Geuvers–Klop conjecture: Is every weakly normalizing pure type system also strongly normalizing?

• Ismultiplicative-exponential linear logic decidable?
• Is theAanderaa–Karp–Rosenberg conjecture true?
• Černý conjecture: If adeterministic finite automaton with${\displaystyle n}$ states has asynchronizing word, must it have one of length at most${\displaystyle (n-1{)}^2}$?
• Generalized star-height problem: Can allregular languages be expressed using generalized regular expressions with a limited nesting depth ofKleene stars?
• Separating words problem: How many states are needed in adeterministic finite automaton that behaves differently on two givenstrings of length${\displaystyle n}$?
• What is theTuring completeness status of all uniqueelementary cellular automata?
• Determine whether the length of the minimal uncompletable word of${\displaystyle M}$ is polynomial in${\displaystyle l(M)}$, or even in${\displaystyle sl(M)}$. It is known that${\displaystyle M}$ is avariable-length code if for all${\displaystyle u_1,...,u_n,v_1,...,v_m\in M}$,${\displaystyle u_1...u_n=v_1...v_m}$ implies${\displaystyle n=m}$ and${\displaystyle u_i=v_i}$ for all. In such cases, we do not yet know if a polynomial bound exists. This is a possible weakening of theRestivo conjecture (already disproven in general, though upper bounds remain unknown).
• Determine all positive integers${\displaystyle n}$ such that the concatenation of${\displaystyle n}$ and${\displaystyle n^2}$ in base${\displaystyle b}$ uses at most${\displaystyle k}$ distinct characters, for fixed${\displaystyle b}$ and${\displaystyle k}$.^{[citation needed]}

Many other problems incoding theory are also listed among theunsolved problems in mathematics.

• Woeginger, Gerhard J."Open problems around exact algorithms".Discrete Applied Mathematics. 156 (2008):397–405.
• The RTA list of open problems – Open problems inrewriting.
• The TLCA List of Open Problems – Open problems in the area oftyped lambda calculus.

• Conjectures
• Lists of unsolved problems
• Unsolved problems in computer science

• Articles with short description
• Short description is different from Wikidata
• Dynamic lists
• All articles with unsourced statements
• Articles with unsourced statements from September 2024
• CS1: long volume value