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

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

Algorithmic number theory

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

Other algorithmic problems

Programming language theory

Other problems

  • Is multiplicative-exponential linear logic decidable?
  • Is the Aanderaa–Karp–Rosenberg conjecture true?
  • Černý conjecture: If a deterministic finite automaton with n {\displaystyle n} states has a synchronizing word, must it have one of length at most ( n − 1 ) 2 {\displaystyle (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 {\displaystyle n}?
  • What is the Turing completeness status of all unique elementary cellular automata?
  • Determine whether the length of the minimal uncompletable word of M {\displaystyle M} is polynomial in l ( M ) {\displaystyle l(M)}, or even in s l ( M ) {\displaystyle sl(M)}. It is known that M {\displaystyle M} is a variable-length code if for all u 1 , . . . , u n , v 1 , . . . , v m ∈ M {\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M}, u 1 . . . u n = v 1 . . . v m {\displaystyle u_{1}...u_{n}=v_{1}...v_{m}} implies n = m {\displaystyle n=m} and u i = v i {\displaystyle u_{i}=v_{i}} for all 0 < i ≤ n {\displaystyle 0<i\leq n}. In such cases, we do not yet know if a polynomial bound exists. This is a possible weakening of the Restivo conjecture (already disproven in general, though upper bounds remain unknown).
  • Determine all positive integers n {\displaystyle n} such that the concatenation of n {\displaystyle n} and n 2 {\displaystyle n^{2}} in base b {\displaystyle b} uses at most k {\displaystyle k} distinct characters, for fixed b {\displaystyle b} and k {\displaystyle k}.[citation needed]

See also

External links