The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.
Contents
- Significance
- Ben Dor and Halevis proof
- Overview
- Constructing the integer graph
- Notable properties of the graph
- The clause component
- 01 Matrix
- Reduction to a non negative matrix
- Reduction to powers of 2
- Reduction to 01
- Aaronsons proof
- References
Valiant's 1979 paper also introduced #P as a complexity class.
Significance
One reason for interest in the computational complexity of the permanent is that it provides an example of a problem where constructing a single solution can be done efficiently but where counting all solutions is hard. As Papadimitriou writes in his book Computational Complexity:
Specifically, computing the permanent (shown to be difficult by Valiant's results) is closely connected with finding a perfect matching in a bipartite graph, which is solvable in polynomial time by the Hopcroft–Karp algorithm. For a bipartite graph with 2n vertices partitioned into two parts with n vertices each, the number of perfect matchings equals the permanent of its biadjacency matrix and the square of the number of perfect matchings is equal to the permanent of its adjacency matrix. Since any 0–1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies that the problem of counting the number of perfect matchings in a bipartite graph is #P-complete, and in conjunction with Toda's theorem this implies that it is hard for the entire polynomial hierarchy.
The computational complexity of the permanent also has some significance in other aspects of complexity theory: it is not known whether NC equals P (informally, whether every polynomially-solvable problem can be solved by a polylogarithmic-time parallel algorithm) and Ketan Mulmuley has suggested an approach to resolving this question that relies on writing the permanent as the determinant of a matrix.
Hartmann proved a generalization of Valiant's theorem concerning the complexity of computing immanants of matrices that generalize both the determinant and the permanent.
Ben-Dor and Halevi's proof
Below, the proof that computing the permanent of a 01-matrix is #P-complete is described. It mainly follows the proof by Ben-Dor & Halevi (1993).
Overview
Any square matrix
#SAT, a function problem related to the Boolean satisfiability problem, is the problem of counting the number of satisfying assignments of a given Boolean formula. It is a #P-complete problem (by definition), as any NP machine can be encoded into a Boolean formula by a process similar to that in Cook's theorem, such that the number of satisfying assignments of the Boolean formula is equal to the number of accepting paths of the NP machine. Any formula in SAT can be rewritten as a formula in 3-CNF form preserving the number of satisfying assignments, and so #SAT and #3SAT are equivalent and #3SAT is #P-complete as well.
In order to prove that 01-Permanent is #P-hard, it is therefore sufficient to show that the number of satisfying assignments for a 3-CNF formula can be expressed succinctly as a function of the permanent of a matrix that contains only the values 0 and 1. This is usually accomplished in two steps:
- Given a 3-CNF formula φ, construct a directed integer-weighted graph
G ϕ G ϕ - Through a series of reductions, reduce Permanent to 01-Permanent, the problem of computing the permanent of a matrix all entries 0 or 1. This establishes that 01-permanent is #P-hard as well.
Constructing the integer graph
Given a 3CNF-formula
- each satisfying assignment for
ϕ will have a corresponding set of cycle covers inG ϕ 12 m - all other cycle covers in
G ϕ
Thus if
The graph construction makes use of a component that is treated as a "black box." To keep the explanation simple, the properties of this component are given without actually defining the structure of the component.
To specify Gφ, one first constructs a variable node in Gφ for each of the n variables in φ. Additionally, for each of the m clauses in φ, one constructs a clause component Cj in Gφ that functions as a sort of "black box." All that needs to be noted about Cj is that it has three input edges and three output edges. The input edges come either from variable nodes or from previous clause components (e.g., Co for some o < j) and the output edges go either to variable nodes or to later clause components (e.g., Co for some
Next, one would consider the edges. For each variable
Note that the graph
Notable properties of the graph
A useful property of
The sort of Z's that don't induce assignments are the ones with cycles that "jump" inside the clause components. That is, if for every
The clause component
To understand the relevant properties of the clause components
Recall that construction of
The clause component is a weighted, directed graph with 7 nodes with edges weighted and nodes arranged to yield the properties specified above, and is given in Appendix A of Ben-Dor and Halevi (1993). Note that the internal edges here have weights drawn from the set
Finally, since the sum of weights of all the sets of cycle covers inducing any particular satisfying assignment is 12m, and the sum of weights of all other sets of cycle covers is 0, one has Perm(Gφ) = 12m·(#φ). The following section reduces computing Perm(
01-Matrix
The above section has shown that Permanent is #P-hard. Through a series of reductions, any permanent can be reduced to the permanent of a matrix with entries only 0 or 1. This will prove that 01-Permanent is #P-hard as well.
Reduction to a non-negative matrix
Using modular arithmetic, convert an integer matrix A into an equivalent non-negative matrix
Let
The transformation of
An example of the transformation and why it works is given below.
Here,
Note how the elements are non-negative because of the modular arithmetic. It is simple to compute the permanent
so
Reduction to powers of 2
Note that any number can be decomposed into a sum of powers of 2. For example,
This fact is used to convert a non-negative matrix into an equivalent matrix whose entries are all powers of 2. The reduction can be expressed in terms of graphs equivalent to the matrices.
Let
This can be seen graphically in the Figure 1. The subgraph that replaces the existing edge contains
To prove that this produces an equivalent graph
Consider some cycle-cover
Note that the size of
Reduction to 0–1
The objective here is to reduce a matrix whose entries are powers of 2 into an equivalent matrix containing only zeros and ones (i.e. a directed graph where each edge has a weight of 1).
Let G be a
This reduction is done locally at each edge in G that has a weight larger than 1. Let
Consider some cycle-cover
Aaronson's proof
Quantum computer scientist Scott Aaronson has proved #P-hardness of permanent using quantum methods.