Top Qs
Timeline
Chat
Perspective

List of unsolved problems in computer science

List of unsolved computational problems From Wikipedia, the free encyclopedia

Remove ads

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

Remove ads

Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

Summarize
Perspective

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]

Remove ads

Other algorithmic problems

Programming language theory

Other problems

Summarize
Perspective
  • Is the Aanderaa–Karp–Rosenberg conjecture true?
  • Černý conjecture: If a deterministic finite automaton with states has a synchronizing word, must it have one of length at most ?
  • 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 ?
  • What is the Turing completeness status of all unique elementary cellular automata?
  • Determine whether the length of the minimal uncompletable word of is polynomial in , or even in . It is known that is a variable-length code if for all , implies and for all . 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 such that the concatenation of and in base uses at most distinct characters, for fixed and .[citation needed]

Many other problems in coding theory are also listed among the unsolved problems in mathematics.

Remove ads

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads