Permanent is sharp-P-complete
Encyclopedia
In a 1979 paper Leslie Valiant
proved that the problem of computing the permanent
of a matrix
is #P-hard, and remains #P-complete even if the matrix is restricted to have entries that are all 0 or 1. This result is sometimes known as Valiant's theorem and is considered a seminal result in computational complexity theory
. Valiant's 1979 paper also introduced #P
as a complexity class
.
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.
can be viewed as the adjacency matrix
of a directed graph, with
representing the weight of the edge from vertex i to vertex j. Then, the permanent of A 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:
with m clauses and n variables, one can construct a weighted, directed graph 
such that
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 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
). The first input and output edges correspond with the first variable of the clause j, and so on. Thus far, all of the nodes that will appear in the graph Gφ 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 draw 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).
is that its cycle covers correspond to variable assignments for 
. For a cycle cover Z of 
, one can say that Z induces an assignment of values for the variables in 
just in case Z 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 Z 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 Z. The term Z is considered an incomplete cycle cover at this stage, because one talks only about its external edges, M. In the section below, one considers M-completions to show that one has a set of cycle covers corresponding to each M that have the necessary properties.
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
, at least one of 
's input edges is in Z, and every output edge of the clause components is in Z when the corresponding input edge is in Z, then Z is proper with respect to each clause component, and Z will produce a satisfying assignment for 
. This is because proper Z's 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 Z's 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 Z's have weight 
, and any other Z's have weight 
. The reasons for this depend on the construction of the clause components, and are outlined below.
, one needs the notion of an M-completion. A cycle cover Z 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 M. Let M be a set of external edges. A set of internal edges L is an M-completion just in case 
is a cycle cover of 
. Further, denote the set of all M-completions by 
and the set of all resulting cycle covers of 
by 
.
Recall that construction of
was such that each external edge had weight 1, so the weight of 
, the cycle covers resulting from any M, depends only on the internal edges involved. We add here the premise that the construction of the clause components is such that the sum over possible M-completions of the weight of the internal edges in each clause component, where M is proper relative to the clause component, is 12. Otherwise the weight of the internal edges is 0. Since there are m clause components, and the selection of sets of internal edges, L, within each clause component is independent of the selection of sets of internal edges in other clause components, so one can multiply everything to get the weight of 
. So, the weight of each 
, where M induces a satisfying assignment, is 
. Further, where M does not induce a satisfying assignment, M is not proper with respect to some 
, so the product of the weights of internal edges in 
will be 
.
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
; not all edges have 0–1 weights.
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(
) to the permanent of a 01 matrix.
, convert an integer matrix A into an equivalent non-negative matrix
so that the permanent of 
can be computed easily from the permanent of 
, as follows:
Let
be an 
integer matrix where no entry has a magnitude larger than 
.
The transformation of
into 
is polynomial in 
and 
, since the number of bits required to represent 
is polynomial in 
and 
An example of the transformation and why it works is given below.
.
Here,
, 
, and 
, so 
. Thus
Note how the elements are non-negative because of the modular arithmetic. It is simple to compute the permanent
so
. Then 
, so 
. 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
be a 
-node weighted directed graph with non-negative weights, where largest weight is 
. Every edge 
with weight 
is converted into an equivalent edge with weights in powers of 2 as follows:
, 
This can be seen graphically in the Figure 1. The subgraph that replaces the existing edge contains
nodes and 
edges.
To prove that this produces an equivalent graph
that has the same permanent as the original, one must show the correspondence between the cycle covers of 
and 
.
Consider some cycle-cover
in 
.
Note that the size of
is polynomial in 
and 
.
Let G be a
-node directed graph where all the weights on edges are powers of two. Construct a graph, 
, where the weight of each edge is 1 and Perm(G) = Perm(G'). The size of this new graph, G', is polynomial in 
and 
where the maximal weight of any edge in graph G is 
.
This reduction is done locally at each edge in G that has a weight larger than 1. Let
be an edge in G with a weight 
. It is replaced by a subgraph 
that is made up of 
nodes and 
edges as seen in Figure 2. Each edge in 
has a weight of 1. Thus, the resulting graph G' contains only edges with a weight of 1.
Consider some cycle-cover
in 
.
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
proved that the problem of computing the permanent
Permanent
The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...
of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
is #P-hard, and remains #P-complete even if the matrix is restricted to have entries that are all 0 or 1. This result is sometimes known as Valiant's theorem and is considered a seminal result in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. Valiant's 1979 paper also introduced #P
Sharp-P
In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
as a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
.
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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, 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
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
. 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
Toda's theorem
Toda's theorem was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...
this implies that it is hard for the entire polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
.
The computational complexity of the permanent also has some significance in other aspects of complexity theory: it is not known whether NC
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
equals P (informally, whether every polynomially-solvable problem can be solved by a polylogarithmic-time parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
) and Ketan Mulmuley
Ketan Mulmuley
Ketan Mulmuley is a professor in the Department of Computer Science at the University of Chicago, and a sometime visiting professor at IIT Bombay...
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 .Overview
Any square matrix can be viewed as the adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of a directed graph, with
representing the weight of the edge from vertex i to vertex j. Then, the permanent of A 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
Sharp-SAT
In computational complexity theory, #SAT, or Sharp-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...
, a function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
related to the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
, 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
Cook's theorem
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete...
, 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
3sat
3sat is the name of a public, advertising-free, television network in Central Europe. The programming is in German and is broadcast primarily within Germany, Austria and Switzerland .3sat was established for cultural...
as a formula in 3-CNF
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
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 m clauses and n 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 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
). The first input and output edges correspond with the first variable of the clause j, and so on. Thus far, all of the nodes that will appear in the graph Gφ 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 draw 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 Z of , one can say that Z induces an assignment of values for the variables in just in case Z 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 Z 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 Z. The term Z is considered an incomplete cycle cover at this stage, because one talks only about its external edges, M. In the section below, one considers M-completions to show that one has a set of cycle covers corresponding to each M that have the necessary properties.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
, at least one of 's input edges is in Z, and every output edge of the clause components is in Z when the corresponding input edge is in Z, then Z is proper with respect to each clause component, and Z will produce a satisfying assignment for . This is because proper Z's 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 Z's 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 Z's have weight , and any other Z's have 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 Z 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 M. Let M be a set of external edges. A set of internal edges L is an M-completion just in case is a cycle cover of . Further, denote the set of all M-completions by and the set of all resulting cycle covers of by .Recall that construction of
was such that each external edge had weight 1, so the weight of , the cycle covers resulting from any M, depends only on the internal edges involved. We add here the premise that the construction of the clause components is such that the sum over possible M-completions of the weight of the internal edges in each clause component, where M is proper relative to the clause component, is 12. Otherwise the weight of the internal edges is 0. Since there are m clause components, and the selection of sets of internal edges, L, within each clause component is independent of the selection of sets of internal edges in other clause components, so one can multiply everything to get the weight of . So, the weight of each , where M induces a satisfying assignment, is . Further, where M does not induce a satisfying assignment, M is not proper with respect to some , so the product of the weights of internal edges in will be .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
; not all edges have 0–1 weights.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(
) to the permanent of a 01 matrix.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 arithmeticModular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
, convert an integer matrix A into an equivalent non-negative matrix
so that the permanent of can be computed easily from the permanent of , as follows:Let
be an integer matrix where no entry has a magnitude larger than .
- Compute
. The choice of Q is due to the fact that 
- Compute
- Compute
- If
then Perm(A) = P. Otherwise 
The transformation of
into is polynomial in and , since the number of bits required to represent is polynomial in and An example of the transformation and why it works is given below.
.Here,
, , and , so . ThusNote how the elements are non-negative because of the modular arithmetic. It is simple to compute the permanent
so
. Then , so Reduction to powers of 2
Note that any number can be decomposed into a sum of powers of 2Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix 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
be a -node weighted directed graph with non-negative weights, where largest weight is . Every edge with weight is converted into an equivalent edge with weights in powers of 2 as follows:, This can be seen graphically in the Figure 1. The subgraph that replaces the existing edge contains
nodes and edges.To prove that this produces an equivalent graph
that has the same permanent as the original, one must show the correspondence between the cycle covers of and .Consider some cycle-cover
in .
- If an edge
is not in 
, then to cover all the nodes in the new sub graph, one must use the self-loops. Since all self-loops have a weight of 1, the weight of cycle-covers in 
and 
match. - If
is in 
, then in all the corresponding cycle-covers in 
, there must be a path from 
to 
, where u and v are the nodes of edge e. From the construction, one can see that there are 
different paths and sum of all these paths equal to the weight of the edge in the original graph 
. So the weight of corresponding cycle-covers in 
and 
match.
Note that the size of
is polynomial in and .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
-node directed graph where all the weights on edges are powers of two. Construct a graph, , where the weight of each edge is 1 and Perm(G) = Perm(G'). The size of this new graph, G', is polynomial in and where the maximal weight of any edge in graph G is .This reduction is done locally at each edge in G that has a weight larger than 1. Let
be an edge in G with a weight . It is replaced by a subgraph that is made up of nodes and edges as seen in Figure 2. Each edge in has a weight of 1. Thus, the resulting graph G' contains only edges with a weight of 1.Consider some cycle-cover
in .
- If an original edge
from graph G is not in 
, one cannot create a path through the new subgraph 
. The only way to form a cycle cover over 
in such a case is for each node in the subgraph to take its self-loop. As each edge has a weight of one, the weight of the resulting cycle cover is equal to that of the original cycle cover. - However, if the edge in G is a part of the cycle cover then in any cycle cover of
there must be a path from 
to 
in the subgraph. At each step down the subgraph there are two choices one can make to form such a path. One must make this choice 
times, resulting in 
possible paths from 
to 
. Thus, there are 
possible cycle covers and since each path has a weight of 1, the sum of the weights of all these cycle covers equals the weight of the original cycle cover.