♯P-completeness of 01-permanent

The #P-completeness of 01-permanent, sometimes known as Valiant's theorem,[1] is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory.

[4] 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.

In this kind of reduction, a single hard instance of some other problem in #P is reduced to computing the permanent of a sequence of multiple graphs, each of which could potentially depend on the results of previous permanent computations.

A later simplification by Ben-Dor & Halevi (1993) showed that it is possible to use a weaker notion of reduction, a polynomial-time counting reduction, that translates the other problem into a single instance of the permanent problem.

[6] As Papadimitriou writes in his book Computational Complexity: The most impressive and interesting #P-complete problems are those for which the corresponding search problem can be solved in polynomial time.

[1]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.

[7][8] 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.

[9] Since any 0–1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies[9] 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.

[10][11] 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.

is equal to the sum of the weights of all cycle-covers of the graph; this is a graph-theoretic interpretation of the permanent.

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.

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.

(Valiant's original proof constructs a graph with entries in

The graph construction makes use of a component that is treated as a "black box."

The input edges come either from variable nodes or from previous clause components (e.g.,

) and the output edges go either to variable nodes or to later clause components (e.g.,

appears, we connect the appropriate output edge of the corresponding clause component back to

Every external edge is part of a T-cycle or an F-cycle (but not both—that would force inconsistency).

, so the construction can be done in polytime (assuming that the clause components do not cause trouble).

that the assignment makes true, and vice versa for all variables

is considered an incomplete cycle cover at this stage, because one talks only about its external edges,

that do not induce assignments are the ones with cycles that "jump" inside the clause components.

The reasons for this depend on the construction of the clause components, and are outlined below.

We add here the premise that the construction of the clause components is such that the sum over possible

clause components, and the selection of sets of internal edges,

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).

Finally, since the sum of weights of all the sets of cycle covers inducing any particular satisfying assignment is

The reduction can be expressed in terms of graphs equivalent to the matrices.

is converted into an equivalent edge with weights in powers of 2 as follows: This can be seen graphically in the Figure 1.

that has the same permanent as the original, one must show the correspondence between the cycle covers of