List of open problems in computer science
   HOME

TheInfoList



Click Here for Items Related To - List of open problems in computer science
OR:
List of open problems in computer science on:   [Wikipedia]   [Google]   [Amazon]

This article is a list of notable unsolved problems in
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. 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. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...
* 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 gam ...
* Is the
exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...
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, spe ...
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 number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
be done in
polynomial time In 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 performed by ...
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 . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
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 clustered planar drawings be found in polynomial time? * 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 compl ...
be solved in polynomial time? * Can
leaf power In the mathematical area of graph theory, a -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induce ...
s and -leaf powers be recognized in polynomial time? * Can
parity game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...
s 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 k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
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 bounded even for dense graphs. It is defined as the minimum num ...
be recognized in polynomial time? * Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time? * Can a
simultaneous embedding Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between a ...
with fixed edges for two given graphs be found in polynomial time?.


Other algorithmic problems

* The dynamic optimality conjecture: do splay trees have a bounded competitive ratio? * Is there a -competitive online algorithm for the -server problem? * 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). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...
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 comparison sort. It can be seen as either a generalization of sorting by exchange ( bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs o ...
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 strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to tr ...
between two strings of length be computed in strongly sub-quadratic time? (This is only possible if the strong
exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...
is false.) * Can
X + Y sorting In computer science, \boldsymbol+\boldsymbol sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparis ...
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 In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomi ...
for
polynomial identity testing In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, ...
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 are represented by linear function#As a polynomial function, li ...
admit a
strongly polynomial In 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 performed by t ...
-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 sha ...
? * What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the
decision tree A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains condit ...
complexity of the MST problem? The optimal algorithm to compute MSTs is
known Knowledge can be defined as awareness of facts or as practical skills, and may also refer to familiarity with objects or situations. Knowledge of facts, also called propositional knowledge, is often defined as true belief that is distinc ...
, but it relies on decision trees, so its complexity is unknown. * Gilbert–Pollack conjecture on the Steiner ratio of the Euclidean plane


Natural language processing algorithms

* Is there any perfect
syllabification Syllabification () or syllabication (), also known as hyphenation, is the separation of a word into syllables, whether spoken, written or signed. Overview The written separation into syllables is usually marked by a hyphen when using English or ...
algorithm in the English language? * Is there any perfect
stemming In linguistic morphology and information retrieval, stemming is the process of reducing inflected (or sometimes derived) words to their word stem, base or root form—generally a written word form. The stem need not be identical to the morpholog ...
algorithm in the English language? * Is there any perfect phrase chunking algorithm in the English language? * How can computers discern pronoun ambiguity in the English Language? (Also known as the
Winograd Schema Challenge The Winograd schema challenge (WSC) is a test of machine intelligence proposed by Hector Levesque, a computer scientist at the University of Toronto. Designed to be an improvement on the Turing test, it is a multiple-choice test that employs questi ...
).


Programming language theory

* POPLmark *
Barendregt–Geuvers–Klop conjecture __NOTOC__ In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and d ...


Other problems

*
Aanderaa–Karp–Rosenberg conjecture In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectures about the number of questions of the form "Is there an ...
* Černý Conjecture * Generalized star-height problem *
Separating words problem In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the othe ...


References


External links


Open problems around exact algorithms
by
Gerhard J. Woeginger Gerhard J. Woeginger (31 May 1964 – 1 April 2022) was an Austrian mathematician and computer scientist who worked in Germany as a professor at RWTH Aachen University, where he chaired the algorithms and complexity group in the department of c ...
, Discrete Applied Mathematics 156 (2008) 397–405.
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 well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
.
The TLCA List of Open Problems
– open problems in area
typed lambda calculus A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a ...
. {{DEFAULTSORT:Unsolved Problems In Computer Science
Computer Science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
Computer Science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...