Complexity Garden

From Complexity Zoo
Revision as of 15:35, 3 March 2015 by Fgrosshans (talk | contribs) (→‎#SAT: Count satisfying truth assignments: Correst red links to {{3-,}CNF-,}SAT)
Jump to navigation Jump to search


Main Zoo - Complexity Garden - Zoo Glossary - Zoo References


Welcome to the Complexity Garden, the botanical companion to the Complexity Zoo. This field guide lists rigorously defined computational problems, together with their relations to complexity classes, their best algorithmic results, and their relations to other problems. There are now 39 problems and (one can only hope) counting. The initial members either have or might have some exotic property related to speedup (such as O-speedup, monotone-nonmonotone gap, or P-nonuniformity), or provide a canonical example of a complexity class (i.e. NP-complete). However, all additions are welcome, and it is hoped that this will grow into a comprehensive collection.

Gardener: Hunter Monroe (volunteers welcome)

To create a new problem, click on the edit link of the problem before or after the one that you want to add and copy the format, and save. The preferred format of each problem is as follows: description of the problem, relations to complexity classes, their best algorithmic results (upper-bounds and lower-bounds e.g. see the Set Cover problem), memberships and properties, and relations to other problems. Then, add the problem to the table of contents and increment the total number of problems. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our simple wiki help page.

If your problem is not on the list and you suspect that it might be an open problem you can check the Open Problem Garden.

Table of Contents

Graph theoretic problems: #Perfect Matching - Clique-Like - Graph Automorphism - Graph Isomorphism - Perfect Matching

Satisfiability problems: #SAT - #WSAT - Constraint Satisfaction - QBF - Quantum k-SAT - SAT - k-SAT - Unique Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT

Sets and partitions: Set Cover

Uncategorized problems: 3SUM - Approximate Shortest Lattice Vector - Boolean Convolution - Boolean Matrix Multiplication - Boolean Sorting - Discrete Logarithm - Equality - Group Nonmembership - Integer Factorization - Integer Factor ≤ k - Integer Multiplication - k-Local Hamiltonians - k-Round Sorting - Linear Programming - Majority - Matrix Multiplication - Parity - Permanent - Ring Automorphism - Ring Isomorphism - Short Implicant - Stochastic Games - Tautology - Square Root mod n - Threshold(k)

The Problems

#Perfect Matching: Count perfect matchings

The #Perfect Matching problem is to count the number of perfect matchings in a bipartite graph. It is the counting version of Perfect Matching.

Algorithms: ?

Memberships: ∈ #P-complete

Related Problems: #Perfect Matching is equivalent to Permanent.

#SAT: Count satisfying truth assignments

This is the counting version of SAT: given a Boolean formula, compute how many satisfying truth assignments it has.

Algorithms: ?

Memberships: ∈ #P-complete

Related Problems: The version #CNF-SAT (counting version of CNF-SAT) and #3-CNF-SAT also called #3SAT (counting version of 3-CNF-SAT) also are two #P-complete problems.

#WSAT: Weighted SAT

Given a Boolean formula, count the number of satisfying assignments of Hamming weight Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . This is the canonical problem for #WT.

Algorithms: ?

Memberships: ∈ #WT


3SUM: Do there exist members of a list satisfying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a+b+c=0} ?

Given a list Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X=\{x_i\}_{i=1}^n} of integers, do there exist elements such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a+b+c=0} ? This problem is important enough to computational geometry that there is defined a class of problems to which it is reducible: 3SUM-hard.

Algorithms: ?

Memberships: ?

Approximate Shortest Lattice Vector: Does the shortest vector exceed kn?

Given a lattice L in Zn and an integer n, does the shortest vector of L have (Euclidean) length at most kn?

Algorithms: ?

Memberships: ∈ NP ∩ coNP, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \notin} P?

Boolean Convolution: Convolution of two n-bit integers.

Compute the convolution of two n-bit integers in binary notation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i+j=k}x_i \cdot y_j} , where the multiplicands are respectively the i-1 and j-1 bits of the two integer inputs, and k is the k-1 bit of the output. It is a Boolean function with n input bits and 2n-1 output bits.

It has monotone circuit complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(n^{3/2})} (Weiss) and nonmonotone circuit complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\log n 2^{O(\log^* n)}} (Furer [Fur07]). Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log^*(n)} means iteratively taking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log} of n until the result is less than 2. Nonmonotone circuits use the discrete Fourier transform (Wegener [Weg87]).

Algorithms: ?

Memberships: ∈ FP
Properties: P-nonuniform?, monotone-nonmonotone gap

Boolean Matrix Multiplication: Monotone product of Boolean matrices

Boolean Matrix Multiplication is a Boolean function with 2n2 input bits (two nxn matrices) and n2 output bits (an nxn matrix). The function is defined using the usual row-column rule, but using OR instead of binary addition.

It has monotone circuit complexity of exactly Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n^3-n^2} (Pratt [Pra74]), but its nonmonotone circuit complexity is the same as matrix multiplication, presently Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^{2.376})} (Wegener [Weg87]).

Algorithms: ?

Memberships: ∈ FP
Properties: P-nonuniform?, monotone-nonmonotone gap

Boolean Sorting: Sort n input bits.

A Boolean function with n inputs and n outputs that puts the 0s before the 1s. For example, 101 → 011 and 11000 → 00011.

It has monotone circuit complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(n \log n)} (Lamagna and Savage [LS74]) and nonmonotone circuit complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(n)} (Muller and Preparata [MP75]). The nonmonotone circuits use binary rather than unary addition to count the 0 inputs.

The outputs are the Threshold(k) functions in reverse order; in particular, the middle output is Majority.

Algorithms: ?

Memberships: ∈ FP
Properties: O-optimal, symmetric, monotone-nonmonotone gap

Clique-Like: Tardos' Clique-like approximation

Clique-Like is a Boolean function with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} inputs (an adjacency matrix) and one output.

It has monotone circuit complexity of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega\left(e^{cn^{1/6-o(1)}}\right)} (Tardos [Tar88]). By contrast it has polynomial nonmonotone circuit complexity, because it reduces to Linear Programming.

Algorithms: ?

Memberships: ∈ P
Properties: monotone-nonmonotone gap

Constraint Satisfaction Problem: Generalized version of satisfiability problems

Given two sets of relations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I,T} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} is the instance (not to be confused with an instance of CSP) and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is the template, over the same vocabulary, where the vocabulary defines the names and arities of allowed relations, is there a mapping Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} such that for all relations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(x_1, x_2, \dots, x_k)\in I} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\left(h(x_1, x_2, \dots, x_k)\right)\in T} ?

Algorithms: ?

Memberships: NP-complete.

See Also: [FV93].

Discrete Logarithm: Reverse exponentiation

The discrete logarithm problem is to solve for x in the equation ax = b in some number-theoretic abelian group, typically either the group of units of a finite field or an elliptic curve over a finite field. Like the related Integer Factorization, the fastest classical algorithm is the number field sieve, with heuristic time complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{O(n^{1/3}(\log n)^{2/3})}} . Also like Integer Factorization, Shor's algorithm solves Discrete Logarithm in quantum polynomial time. In fact, Shor's algorithm solves Discrete Logarithm even in a black-box abelian group, provided that group elements have unique names.

Algorithms: ?

Memberships: ∈ FNP ∩ FBQP
Properties: Is a one-way function?

Equality: Are two strings equal?

If Alice has a string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in\left\{0,1\right\}^n} and Bob has a string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y\in\left\{0,1\right\}^n} , define EQUALITY(x, y) = 1 if and only if x = y.

Algorithms: ?

Memberships:

Graph Automorphism: Is there a nontrivial automorphism?

Graph Automorphism is equivalent to Graph Isomorphism in the case where the two graphs are identical.

Algorithms: ?

Memberships: ∈ NP ∩ coAM.

Graph Isomorphism: Are two graphs isomorphic?

Given two graphs, are they isomorphic, i.e., is there a bijection between their vertices which preserves edges?

Luks showed that Graph Isomorphism for bounded-valence graphs is in P non-uniformly (the exponent of algorithm's running time depends on the bound). Combining Luks' algorithm with a trick due to Zemlyachenko yields a time complexity upper bound of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{O(\sqrt{v \log v})}} for graphs with v vertices. However, some practical Graph Isomorphism algorithms, such as NAUTY, seem to run much faster than this rigorous upper bound.

Like Perfect Matching, it is not known to be complete for a natural complexity class.

Algorithms: ?

Memberships: ∈ NP ∩ coAM, P-nonuniform?

Properties: In NP\P but not NP-complete?

Group Non-Membership: Is an element of G a member of a subgroup H?

Defined by [Wat00]. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} be a group, whose elements are represented by polynomial-size strings. We're given a "black box" that correctly multiplies and inverts elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Then given elements Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\in G} and , we can asked to find if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\notin\left\langle h_1, \dots, h_k \right\rangle} (the subgroup generated by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_1,\dots,h_k\in G} ).

Algorithms: ?

Memberships: QMA [Wat00].

Hamiltonian circuit: Exists one Hamiltonian circuit?

Given a Graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , exists one Hamiltonian circuit in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ?

Algorithms: ?

Memberships: NP-complete

Integer Factorization: Find an integer's prime factors

Algorithms: The fastest known algorithm for integer factorization is the number field sieve. It has heuristic randomized time complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{O(n^{1/3}(\log n)^{2/3})}} for inputs with n digits.

On the other hand, Shor's algorithm famously solves Integer Factorization in quantum polynomial time.

Memberships: ∈ FNP ∩ FBQP

Properties: In NP\P but not NP-complete?

Integer Factor ≤ k : Is there a factor ≤ k?

With an upper bound on the desired prime factor, this problem is subtly different from Integer Factorization.

Algorithms: The fastest algorithm is either the number field sieve or Lenstra's elliptic curve method, depending on the relative size of n and k. Lenstra's algorithm has heuristic randomized time complexity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{poly}(n)2^{O(\sqrt{k(\log k))})}} if n and k have n and k digits, respectively.

Memberships: ∈ NP ∩ coNP

Integer Multiplication: Product of two n-bit integers

Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM, but is thought to have O-speedup on Turing machines or P-uniform Boolean circuits.

Algorithms: ?

Memberships: ∈ FP
Properties: P-nonuniform?

k-Local Hamiltonians: Find the smallest eigenvalue of m k-local Hamiltonians acting on n qubits.

Given an n-qubit Hilbert space, as well as a collection H1,...,Hm of Hamiltonians (i.e. Hermitian positive semidefinite matrices), each of which acts on at most k qubits of the space. Also given real numbers a,b such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b-a \in \Theta(1/\mathsf{poly}(n))} . Decide whether the smallest eigenvalue of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H=\sum_{i=1}^m H_i} is less than a or greater than b, promised that one of these is the case.

Algorithms: ?

Memberships: ?

Properties:

k-Round Sorting: Sort inputs in ≤ k rounds

There are k-round sorting networks not known to be constructible in deterministic polynomial time which outperform the best-known networks constructible in deterministic polynomial time [GGK03].

Algorithms: ?

Memberships: ?

Properties: P-nonuniform?

Linear Programming: Maximize a linear function with linear constraints

The Linear Programming problem is to maximize a linear function in a convex polytope. It was famously shown to be in FP by Leonid Khachiyan by means of the ellipsoid method. The main algorithms used in practice are simplex and interior-point methods.

Algorithms: ?

Memberships: ∈ FP

Majority: Are most inputs 1?

Majority is a Boolean function with n input bits and 1 output bit. The output is 1 if the majority of input bits are 1. Examples: 001 → 0, 1100 → 1.

MajorityFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \in} P. Majority Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \notin} REG. Therefore, REGFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \subsetneq} P.

Algorithms: ?

Memberships: ∈ P
Properties: O-optimal, symmetric.

Related Problems: See also Boolean Sorting and the Complexity Zoology entry.

Matrix Multiplication: Multiply two Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times n} matrices

Multiply two dense Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times n} matrices over a field Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . Matrix Multiplication has O-speedup among Strassen-type bilinear algorithms [CW82]. Determining the minimal number of multiplications needed to compute a bilinear form (of which Matrix Multiplication is one) is NP-complete ([Has90]). This suggests that Matrix Multiplication is P-nonuniform over bilinear algorithms if NPFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neq} coNP.

If the group-theoretic algorithms of Cohn et al can perform Matrix Multiplication in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} , then Matrix Multiplication has O-speedup among algorithms of the type they consider [CKSU05].

Algorithms:

Memberships: ∈ FP
Properties: O-speedup?, P-nonuniform?

Parity: Is the number of 1 inputs odd?

Parity is a Boolean function with n inputs and 1 output. The output is 1 if the number of 1 inputs is odd. Examples: 001 → 1, 11011 → 0.

ParityFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \in} P. Parity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \notin} FO ([Ajt83] and [FSS84]). Therefore, FOFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \subsetneq} P.

Algorithms: ?

Memberships: ∈ P
Properties: O-optimal, symmetric.

Related Problems: Equals XOR. See the Complexity Zoology entry.

Perfect Matching: Is there a perfect matching?

Perfect Matching is a Boolean function with n2 inputs (an adjacency matrix) describing a bipartite graph and one output which is 1 if the graph has a perfect matching.

Perfect Matching reduces to Linear Programming, and is therefore in P, although specialized algorithms are also known.

It has monotone circuit complexity of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\Omega(\log n)}} (Razborov [Raz85b]) but polynomial nonmonotone circuit complexity.

Perfect Matching is nonuniformly reducible to determinant and is in RNC and [MVV87], [KUW86], but no deterministic NC algorithm is known.

Like Graph Isomorphism, it is not known to be complete for a natural complexity class. There is a randomized or nonuniform log-space reduction of Perfect Matching to Graph Isomorphism [Tor00].

Algorithms: ?

Memberships: ∈ P
Properties: monotone-nonmonotone gap, P-nonuniform?.

Permanent: What is a 0-1 matrix's permanent

The permanent of an n-by-n 0-1 matrix (ai,j) is defined as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{\sigma}\prod_{i=1}^n a_{i,\sigma(i)}} where σ ranges over all permutations of the numbers 1, 2, ..., n. The value of the permanent is equivalent to #Perfect Matching

Algorithms:

Memberships: ∈ #P

Properties: #P-complete

Ring Automorphism: Does a ring have non-trivial an automorphism?

A special case of Ring Isomorphism where the two rings investigated are the same, and where we are looking for non-trivial automorphisms.

Ring Isomorphism: Are two rings isomorphic?

Given two rings, are they isomorphic to each other? The counting version of the problem, #RI, asks how many different isomorphisms exist between the two rings.

Algorithms: ?

Memberships: NP ∩ coAM [KS05].

QBF: Quantified Boolean Formula

Given a Boolean formula with universal and existential quantifiers, is it true? Quantified Boolean Formula (QBF) is the canonical PSPACE-complete problem.

Note that [Pap94] calls this problem QSAT to emphasize its relationship to SAT. In particular, any instance of QBF can be written as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists x_1 \forall x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n)} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is a Boolean formula as in SAT, and where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_n} is either a universal or existential qualifier, depending on whether is even or odd. This characterization lends itself well as a candidate for reductions from two-player games.

Algorithms: ?

Memberships: ∈ PSPACE

Quantum k-SAT: Quantum Analog for SAT

Given a set of measurements, each i of which involves no more than k qubits and accepts with probability Pi, and given the promise that either there exists a state such that the number of accepting measurements is "very large," or that for all states, the number of accepting measurements is very small. We are asked which of the two promise conditions holds.

Algorithms: ?

Properties: QMA-complete for k = 3.

See also: Democritus Lecture 13.

SAT: Is there a satisfying truth assignment?

The SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.

Algorithms: ?

Memberships: ∈ NP-complete

Set Cover: Cover a set with some of its subsets

Given a universe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{U}} and a family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{S}} of subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{U}} , a cover is a subfamily Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}\subseteq\mathcal{S}} of sets whose union is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{U}} . In the set covering decision problem, the input is a pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{U},\mathcal{S})} and an integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ; the question is whether there is a set covering of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} or less. In the set covering optimization problem, the input is a pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{U},\mathcal{S})} , and the task is to find a set covering that uses the fewest sets.

Algorithms: A simple greedy algorithm yields an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(l)} -approximation (and hence, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\ln(l)+1)} -approximation)where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} is the size of largest subset in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{S}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(l)} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} th Harmonic number.

Set covering cannot be approximated in polynomial time to within a factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigl(1-o(1)\bigr)\cdot\ln{n}} , unless NP has quasi-polynomial time algorithms [Fie98]. In addition, Set covering cannot be approximated in polynomial time to within a factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c\cdot\ln{n}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} is a constant, unless PFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle =} NP. The largest value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} is proved in [AMS06].

Memberships: Decision problem ∈ NP-complete, Optimization problem ∈ NP Optimization

= Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT: Satisfiability with clauses of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}

For some natural number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , an instance of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT is an instance of SAT in conjunctive normal form (CNF) where all clauses are the logical OR of Boolean variables.

Algorithms: ?

Memberships: It is known that 2SAT is in P while 3SAT is in NP-complete. }}


Short Implicant: Is there a short implicant?

Given a DNF expression Φ, is there a conjunction of at most k negated or non-negated literals that implies Φ?

Algorithms: ?

Memberships: GC-complete

Stochastic Games: Is there a first player advantage?

White, Black, and Nature alternate moving a token on the edges of a directed graph. Nature's moves are random. Given a graph, start and target nodes for the token, does White have a strategy which will make the token reach the target with probability ≥ 1/2?

Algorithms: ?

Memberships: ∈ NP ∩ coNP, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \notin} P?

Tautology: Are all truth assignments satisfying?

Tautology is coNP-complete.

Algorithms: ?

Memberships: ∈ coNP

Properties: p-speedup? (If so then NP Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neq} coNP)

Square Root mod n: Find square roots mod n

The Square Root mod n problem is to solve for x in the equation x2 = a mod N. Rabin noted that Integer Factorization BPP-reduces to Square Root mod n and vice-versa; the problems are equivalent.

Algorithms: ?

Memberships: ∈ FP

Properties: Is a one-way function?

Threshold(k): Are ≥ k inputs 1?

Threshold(k) is a Boolean function with n input bits and one output bit.

Boolean Sorting is equivalent to the n Threshold(k) functions in reverse order. Majority is equivalent to Threshold(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lceil n/2\rceil} ).

Algorithms: ?

Memberships: ∈ P
Properties: symmetric.

Unique k-SAT: k-SAT with uniqueness promise.

The Unique Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT problem is a promise problem variant of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT, where the promise is that each instance has either no satisfying assignment, or has exactly one satisfying assignment.

Intuitively, adding this promise restricts us to only the hardest instances, as the more satisfying assignments there are, the easier it should be to find one. This intuition is justified by [CIK+03], where it is also shown that if Unique Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT can be solved in deterministic time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(2^{\epsilon n})} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon>0} , then so can Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -SAT for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\ge 3} .

Algorithms: ?

Memberships: ?

Retrieved from "https://complexityzoo.net/index.php?title=Complexity_Garden&oldid=6323"