The #P-completeness of 01-permanent, sometimes known as Valiant's theorem,Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. . Page 443 is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory.Allen Kent, James G. Williams, Rosalind Kent and Carolyn M. Hall (editors). Encyclopedia of microcomputers.Marcel Dekker, 1999. ; p. 34Jin-Yi Cai, A. Pavan and D. Sivakumar, On the Hardness of Permanent. In: STACS, '99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4–6, 1999 Proceedings. pp. 90–99. Springer-Verlag, New York, LLC Pub. Date: October 2007. ; p. 90. In 1979, 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.

Valiant's 1979 paper also introduced #P as a complexity class.Lance Fortnow. My Favorite Ten Complexity Theorems of the Past Decade. Foundations of Software Technology and Theoretical Computer Science: Proceedings of the 14th Conference, Madras, India, December 15–17, 1994. P. S. Thiagarajan (editor), pp. 256–275, Springer-Verlag, New York, 2007. ; p. 265

Valiant's definition of completeness, and his proof of completeness of 01-permanent, both used polynomial-time Turing reductions. 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 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.

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.John E. Hopcroft, Richard M. Karp: An Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4), 225–231 (1973) 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 impliesDexter Kozen. The Design and Analysis of Algorithms. Springer-Verlag, New York, 1991. ; pp. 141–142 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.Seinosuke Toda. PP is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, Volume 20 (1991), Issue 5, pp. 865–877.

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.Ketan Mulmuley. Lower Bounds in a Parallel Model without Bit Operations. SIAM Journal on Computing, Volume 28 (1999), Issue 4, pp. 1460–1509.

Hartmann W. Hartmann. On the complexity of immanants. Linear and Multilinear Algebra 18 (1985), no. 2, pp. 127–140. 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 .

Overview Any square matrix can be viewed as the adjacency matrix of a directed graph, with representing the weight of the edge from vertex to vertex . Then, the permanent of is equal to the sum of the weights of all cycle-covers of the graph; this is a graph-theoretic interpretation of the permanent.

#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 , such that the sum of the weights of cycle covers of (or equivalently, the permanent of its adjacency matrix) is equal to the number of satisfying assignments of . This establishes that Permanent is #P-hard. 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 with clauses and variables, one can construct a weighted, directed graph such that each satisfying assignment for will have a corresponding set of cycle covers in where the sum of the weights of cycle covers in this set will be ; and all other cycle covers in will have weights summing to 0. Thus if is the number of satisfying assignments for , the permanent of this graph will be . (Valiant's original proof constructs a graph with entries in whose permanent is where is "twice the number of occurrences of literals in " – .)

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 , one first constructs a variable node in for each of the variables in . Additionally, for each of the clauses in , one constructs a clause component in that functions as a sort of "black box." All that needs to be noted about 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., for some ) and the output edges go either to variable nodes or to later clause components (e.g., for some ). The first input and output edges correspond with the first variable of the clause , and so on. Thus far, all of the nodes that will appear in the graph have been specified.

Next, one would consider the edges. For each variable of , one makes a true cycle (T-cycle) and a false cycle (F-cycle) in . To create the T-cycle, one starts at the variable node for and draws an edge to the clause component that corresponds to the first clause in which appears. If is the first variable in the clause of corresponding to , this edge will be the first input edge of , and so on. Thence, draw an edge to the next clause component corresponding to the next clause of in which appears, connecting it from the appropriate output edge of to the appropriate input edge of the next clause component, and so on. After the last clause in which appears, we connect the appropriate output edge of the corresponding clause component back to 's variable node. Of course, this completes the cycle. To create the F-cycle, one would follow the same procedure, but connect 's variable node to those clause components in which ~ appears, and finally back to 's variable node. All of these edges outside the clause components are termed external edges, all of which have weight 1. Inside the clause components, the edges are termed internal edges. Every external edge is part of a T-cycle or an F-cycle (but not both—that would force inconsistency).

Note that the graph is of size linear in , so the construction can be done in polytime (assuming that the clause components do not cause trouble).

Notable properties of the graph

A useful property of is that its cycle covers correspond to variable assignments for . For a cycle cover of , one can say that induces an assignment of values for the variables in just in case contains all of the external edges in 's T-cycle and none of the external edges in 's F-cycle for all variables that the assignment makes true, and vice versa for all variables that the assignment makes false. Although any given cycle cover need not induce an assignment for , any one that does induces exactly one assignment, and the same assignment induced depends only on the external edges of . The term is considered an incomplete cycle cover at this stage, because one talks only about its external edges, . In the section below, one considers -completions to show that one has a set of cycle covers corresponding to each that have the necessary properties.

The sort of covers that do not induce assignments are the ones with cycles that "jump" inside the clause components. That is, if for every , at least one of 's input edges is in , and every output edge of the clause components is in when the corresponding input edge is in , then is proper with respect to each clause component, and will produce a satisfying assignment for . This is because proper covers contain either the complete T-cycle or the complete F-cycle of every variable in as well as each including edges going into and coming out of each clause component. Thus, these covers assign either true or false (but never both) to each and ensure that each clause is satisfied. Further, the sets of cycle covers corresponding to all such have weight , and any other has weight . The reasons for this depend on the construction of the clause components, and are outlined below.

The clause component

To understand the relevant properties of the clause components , one needs the notion of an M-completion. A cycle cover induces a satisfying assignment just in case its external edges satisfy certain properties. For any cycle cover of , consider only its external edges, the subset . Let be a set of external edges. A set of internal edges is an -completion just in case is a cycle cover of . Further, denote the set of all -completions by and the set of all resulting cycle covers of by .