The Complexity of Computing the Permanent

By Leslie G. Valiant. 1979

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “Computationally, obtaining the permanent of a matrix is #P-complete [Valiant, 1979], making the permanental process difficult to work with in practice.”
Alignment by Agreement (2006, methodology): “Unfortunately, for even very simple models such as IBM 1 or 2, computing the normalization constant over this set of alignments is a # P -complete problem, by a reduction from counting matchings in a bipartite graph (Valiant, 1979).”
A survey of Pfaffian orientations of graphs (2006, background): “More precisely, Valiant [63] has shown that computing the permanent is #P-complete even when restricted to 0-1 matrices.”
The Computational Complexity of Immanants (2000, methodology): “This hypothesis is supported by Valiant’s famous result [23] stating that the problem to evaluate the permanent of a matrix with entries in {0, 1} is #Pcomplete, as well as his analogous VNP-completeness result [22] in a framework of algebraic computations.”
Learning Bilingual Lexicons from Monolingual Corpora (2008, methodology): “To perform a conventional E-step, we would need to compute the posterior over all matchings, which is #P-complete (Valiant, 1979).”
Structured Prediction via the Extragradient Method (2005, background): “However, computing the partition function Zw(x) is #P-complete [23, 10] for the two structured prediction problems we presented above, matchings and min-cuts.”
The Algorithm Design Manual (2020, background): “The problem of computing the permanent was shown to be #P-complete by Valiant [Val79], where”
Exponentially many perfect matchings in cubic graphs (2010, background): “In general graphs, this problem is ♯P -complete [17].”
The NP-Completeness Column: An Ongoing Guide (1982, background): “(See [29,30] or Chapter 7 of [G&J] for a discussion of such ‘‘#P-completeness’’ results.”
Randomized algorithms (1995, unknown): “Algorithm 3 inserts an element x into H .”
Online Matching and Ad Allocation (2013, background): “Furthermore, the definition of the class #P is also closely related to matching theory, as Valiant [90] proved that finding the number of perfect matchings in a graph (equivalently, the Permanent of a matrix) is NP -hard, and in fact complete for #P .”
Classical simulation of noninteracting-fermion quantum circuits (2001, background): “The permanent is a much harder object to calculate exactly than the determinant of the fermion case, in fact this has been proved to be an #P -complete problem [17].”
Random Generation of Combinatorial Structures from a Uniform Distribution (1986, background): “(Essentially, # P is the class of counting problems associated with p-relations [14].”