Graph isomorphism complexity
Two graphs can look different because their vertices have different names. Can we always decide efficiently whether they have the same connections?
Algorithms and data structures
Within Algorithms and data structures · Search all subjects
Matrix multiplication exponent
Multiplying two square matrices seems to require more work than writing their answer. Is the best possible asymptotic exponent actually two?
Classical integer factorization
77 = 7 × 11 is easy to check. Can a classical computer find the complete prime factorization of every integer efficiently as its written length grows?
All-pairs shortest paths complexity
Can exact shortest-path distances between every pair of vertices in a general weighted graph be computed in truly subcubic time?
Splay tree dynamic optimality
A splay tree reorganizes itself after searches. Is its total cost always within a constant factor of the best search tree that knows all requests in advance?
3SUM hypothesis
Can finding three integers with a specified additive relation be done faster than essentially quadratic time?
Online matrix–vector multiplication
Can a fixed Boolean matrix answer a sequence of arriving vectors in truly subcubic total time when each answer is needed before the next vector arrives?
Deterministic prime construction
Can an algorithm reliably construct a prime of any requested bit length in polynomial time without randomness?
Metric TSP subtour integrality gap
How much can the best traveling-salesperson tour cost exceed its standard fractional relaxation in the worst metric instance?
Small-Set Expansion hypothesis
Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?
Densest-k-subgraph approximation
Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?
Polynomial-time parity-game solving
Can the winner of every finite parity game be determined in polynomial time?
Černý conjecture
Can every synchronizing n-state automaton be reset with at most (n−1)² input symbols?
Hypergraph dualization
Can a classical polynomial-time algorithm recognize all minimal hitting sets?
Bag containment of conjunctive queries
Can an algorithm decide whether one database query always produces each answer no more often than another?
Positivity problem for linear recurrences
Can an algorithm decide whether an integer sequence defined by a linear recurrence never becomes negative?
Deterministic NC perfect matching
Can a deterministic parallel algorithm find a perfect matching in every general graph with polylogarithmic time and polynomially many processors?
Exact edit-distance complexity
Can the exact number of edits between two strings be computed in O(n^(2−ε)) worst-case time for some fixed ε > 0?
Directed feedback vertex set approximation
Can a polynomial-time algorithm remove all directed cycles while deleting at most a fixed multiple of the minimum possible vertex cost?
#BIS approximability
Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?
Constant-factor treewidth approximation
Can a polynomial-time algorithm find a tree decomposition whose largest bag is within a fixed factor of the smallest possible?
Deterministic distributed maximal independent set
Can a network choose a maximal group of nonadjacent nodes in logarithmically many communication rounds without randomness?
Worst-case trace reconstruction
Do polynomially many independently damaged copies always suffice to recover every unknown binary string exactly?
Li–Li network coding conjecture
Several senders share a network of two-way links. Can mixing their messages inside the network ever carry more independent traffic than forwarding and splitting the messages along paths?