HOME

TheInfoList



OR:

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

*
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 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 Isaa ...
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 true? ** Is the strong exponential time hypothesis (SETH) true? * Do one-way functions exist? ** Is public-key cryptography possible? * Log-rank conjecture


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 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 be solved in polynomial time? * Can leaf powers 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 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 tr ...
s be computed in polynomial time? * Can graphs of bounded clique-width 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?.


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 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 of ...
with a deterministic, fixed gap sequence? * Can
3SUM In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A generalized version, ''k''-SUM, asks the same question on ''k'' numbers. 3SUM can be easily solved in O(n^2) t ...
be solved in strongly sub-quadratic time, that is, in time for some ? * Can the edit distance 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 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 are represented by linear relationships. Linear programming is ...
admit a strongly polynomial-time algorithm? (This is problem #9 in Smale's list of problems.) * How many queries are required for envy-free cake-cutting? * What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree 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–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 o ...
algorithm in the English language? * Is there any perfect stemming 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 quest ...
).


Programming language theory

* POPLmark * Barendregt–Geuvers–Klop conjecture


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


References


External links


Open problems around exact algorithms
by Gerhard J. Woeginger, 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 redu ...
.
The TLCA List of Open Problems
– open problems in area typed lambda calculus. {{DEFAULTSORT:Unsolved Problems In Computer Science Computer Science Computer Science