HOME

TheInfoList



OR:

This article is a list of notable unsolved problems in
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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 The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...
– 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. * 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 In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of g ...
* Is the exponential time hypothesis true? ** Is the strong exponential time hypothesis (SETH) true? * Do
one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...
s exist? ** Is
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
possible? * Log-rank conjecture


Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

* Can
integer factorization In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
be done in
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
on a classical (non-quantum) computer? * Can the
discrete logarithm In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...
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 The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational c ...
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. * Is graph canonization polynomial-time equivalent to the graph isomorphism problem? * Can leaf powers and -leaf powers be recognized in polynomial time? * Can parity games be solved in polynomial time? * Can the
rotation distance In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial e ...
between two
binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
s be computed in polynomial time? * Can graphs of bounded
clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of ...
be recognized in polynomial time? * Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time? * Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time? * Can the
square-root sum problem The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry. Definitions SRS is defined as follows:Given positive integers a_1,\ldots,a_k and an intege ...
be solved in polynomial time in the Turing machine model?


Other algorithmic problems

* 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 A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
be computed in time? * What is the fastest algorithm for multiplication of two ''n''-digit numbers? * What is the lowest possible average-case time complexity of
Shellsort Shellsort, also known as Shell sort or Shell's method, is an in-place algorithm, in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method s ...
with a deterministic fixed gap sequence? * Can 3SUM be solved in strongly sub-quadratic time, that is, in time for some ? * Can the
edit distance In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two String (computing), strings (e.g., words) are to one another, that is measured by counting the minimum number of opera ...
between two strings of length be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.) * Can
X + Y sorting X, or x, is the twenty-fourth Letter (alphabet), letter of the Latin alphabet, used in the English alphabet, modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is Wikt:ex#En ...
be done in 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 for some ? * Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized? * Does
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
admit a
strongly polynomial In computer science, a '' polynomial-time algorithm'' is generally speaking an algorithm whose running time is upper-bounded by some polynomial function of the input size. The definition naturally depends on the computational model, which determi ...
-time algorithm? (This is problem #9 in Smale's list of problems.) * How many queries are required for
envy-free cake-cutting An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sh ...
? * What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the
decision tree A decision tree is a decision support system, decision support recursive partitioning structure that uses a Tree (graph theory), tree-like Causal model, model of decisions and their possible consequences, including probability, chance event ou ...
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 In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
equal to 2/\sqrt?


Programming language theory

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


Other problems

* Is the Aanderaa–Karp–Rosenberg conjecture true? * Černý conjecture: If a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state auto ...
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 language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s be expressed using generalized regular expressions with a limited nesting depth of
Kleene star In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...
s? * Separating words problem: How many states are needed in a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state auto ...
that behaves differently on two given strings of length n? * What is the
Turing completeness In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can b ...
status of all unique elementary cellular automata? * Determine whether the length of the minimal uncompletable word of M is polynomial in l(M), or even in sl(M). It is known that M is a
variable-length code In coding theory, a variable-length code is a code which maps source symbols to a ''variable'' number of bits. The equivalent concept in computer science is '' bit string''. Variable-length codes can allow sources to be compressed and decompr ...
if for all u_1,...,u_n,v_1,...,v_m \in M, u_1...u_n = v_1...v_m implies n = m and u_i = v_i for all 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 such that the concatenation of n and n^2 in base b uses at most k distinct characters, for fixed b and k. Many other problems in
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
are also listed among the
unsolved problems in mathematics Many mathematical problems have been stated but not yet solved. These problems come from many areas of mathematics, such as theoretical physics, computer science, algebra, analysis, combinatorics, algebraic, differential, discrete and Eucli ...
.


References


External links

*
The RTA list of open problems
– Open problems in
rewriting In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
.
The TLCA List of Open Problems
– Open problems in the area of typed lambda calculus. {{DEFAULTSORT:Unsolved Problems In Computer Science
Computer Science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
Computer Science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...