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 practical disciplines (includin ...

. 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 * What is the relationship between

BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...

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

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

true? ** Is the strong exponential time hypothesis (SETH) true? * Do one-way functions 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 a ...

possible? * Log-rank conjecture

Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

* Can integer factorization 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' ...

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

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

s and -leaf powers be recognized in polynomial time? * Can parity games be solved in polynomial time? * Can the rotation distance 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) binar ...

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

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

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

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

algorithm in the English language? * Is there any perfect

phrase chunking Phrase chunking is a phase of natural language processing that separates and segments a sentence into its subconstituents, such as noun, verb, and prepositional phrases, abbreviated as NP, VP, and PP, respectively. Typically, each subconstituent or ...

algorithm in the English language? * How can computers discern pronoun ambiguity in the English Language? (Also known as the Winograd Schema Challenge).

Programming language theory

POPLmark In programming language theory, the POPLmark challenge (from "Principles of Programming Languages benchmark", formerly Mechanized Metatheory for the Masses!) (Aydemir, 2005) is a set of benchmarks designed to evaluate the state of automated reaso ...

* Barendregt–Geuvers–Klop conjecture

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

, 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 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 area

typed lambda calculus A typed lambda calculus is a typed formalism (mathematics), 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 term ...

. {{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 practical disciplines (includin ...