 Permanent is sharpPcomplete

The correct title of this article is Permanent is #Pcomplete. The substitution or omission of the # sign is because of technical restrictions.
In a 1979 paper Leslie Valiant proved^{[1]} that the problem of computing the permanent of a matrix is #Phard, and remains #Pcomplete even if the matrix is restricted to have entries that are all 0 or 1. This result is sometimes known as Valiant's theorem^{[2]} and is considered a seminal result in computational complexity theory.^{[3]}^{[4]} Valiant's 1979 paper also introduced #P as a complexity class.^{[5]}
Contents
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.^{[6]} As Papadimitriou writes in his book Computational Complexity:
“ The most impressive and interesting #Pcomplete problems are those for which the corresponding search problem can be solved in polynomial time. The PERMANENT problem for 0–1 matrices, which is equivalent to the problem of counting perfect matchings in a bipartite graph [...] is the classic example here.^{[2]} ” 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 #Pcomplete, 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 polynomiallysolvable problem can be solved by a polylogarithmictime 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.^{[citation needed]}
Hartmann ^{[12]} proved a generalization of Valiant's theorem concerning the complexity of computing immanants of matrices that generalize both the determinant and the permanent.
BenDor and Halevi's proof
Below, the proof that computing the permanent of a 01matrix is #Pcomplete is described. It mainly follows the proof by BenDor & Halevi (1993).^{[13]}
Overview
Any square matrix A = (a_{ij}) can be viewed as the adjacency matrix of a directed graph, with a_{ij} 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 cyclecovers of the graph; this is a graphtheoretic 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 #Pcomplete 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 3CNF form preserving the number of satisfying assignments, and so #SAT and #3SAT are equivalent and #3SAT is #Pcomplete as well.
In order to prove that 01Permanent is #Phard, it is therefore sufficient to show that the number of satisfying assignments for a 3CNF 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 3CNF formula φ, construct a directed integerweighted graph G_{ϕ}, such that the sum of the weights of cycle covers of G_{ϕ} (or equivalently, the permanent of its adjacency matrix) is equal to the number of satisfying assignments of φ. This establishes that Permanent is #Phard.
 Through a series of reductions, reduce Permanent to 01Permanent, the problem of computing the permanent of a matrix all entries 0 or 1. This establishes that 01permanent is #Phard as well.
Constructing the integer graph
Given a 3CNFformula ϕ with m clauses and n variables, one can construct a weighted, directed graph G_{ϕ} such that
 each satisfying assignment for ϕ will have a corresponding set of cycle covers in G_{ϕ} where the sum of the weights of cycle covers in this set will be 12^{m} ; and
 all other cycle covers in G_{ϕ} 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 { − 1,0,1,2,3} whose permanent is where t(ϕ) is "twice the number of occurrences of literals in ϕ" – m.)
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 C_{j} in G_{φ} that functions as a sort of "black box." All that needs to be noted about C_{j} 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., C_{o} for some o < j) and the output edges go either to variable nodes or to later clause components (e.g., C_{o} for some o > j). 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 x_{i} of ϕ, one makes a true cycle (Tcycle) and a false cycle (Fcycle) in G_{ϕ}. To create the Tcycle, one starts at the variable node for x_{i} and draw an edge to the clause component C_{j} that corresponds to the first clause in which x_{i} appears. If x_{i} is the first variable in the clause of ϕ corresponding to C_{j}, this edge will be the first input edge of C_{j}, and so on. Thence, draw an edge to the next clause component corresponding to the next clause of ϕ in which x_{i} appears, connecting it from the appropriate output edge of C_{j} to the appropriate input edge of the next clause component, and so on. After the last clause in which x_{i} appears, we connect the appropriate output edge of the corresponding clause component back to x_{i}'s variable node. Of course, this completes the cycle. To create the Fcycle, one would follow the same procedure, but connect x_{i}'s variable node to those clause components in which ~x_{i} appears, and finally back to x_{i}'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 Tcycle or an Fcycle (but not both—that would force inconsistency).
Note that the graph G_{ϕ} 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 G_{ϕ} is that its cycle covers correspond to variable assignments for ϕ. For a cycle cover Z of G_{ϕ}, 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 x_{i}'s Tcycle and none of the external edges in x_{i}'s Fcycle for all variables x_{i} that the assignment makes true, and vice versa for all variables x_{i} 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 Mcompletions 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 C_{j}, at least one of C_{j}'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 Tcycle or the complete Fcycle of every variable x_{i} 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 x_{i} and ensure that each clause is satisfied. Further, the sets of cycle covers corresponding to all such Z's have weight 12^{m}, and any other Z's have weight 0. 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 C_{j}, one needs the notion of an Mcompletion. A cycle cover Z induces a satisfying assignment just in case its external edges satisfy certain properties. For any cycle cover of G_{ϕ}, consider only its external edges, the subset M. Let M be a set of external edges. A set of internal edges L is an Mcompletion just in case is a cycle cover of G_{ϕ}. Further, denote the set of all Mcompletions by L^{M} and the set of all resulting cycle covers of G_{ϕ} by Z^{M}.
Recall that construction of G_{ϕ} was such that each external edge had weight 1, so the weight of Z^{M}, 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 Mcompletions 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 Z^{M}. So, the weight of each Z^{M}, where M induces a satisfying assignment, is 12^{m}. Further, where M does not induce a satisfying assignment, M is not proper with respect to some C_{j}, so the product of the weights of internal edges in Z^{M} will be 0.
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 BenDor and Halevi (1993). Note that the internal edges here have weights drawn from the set { − 1,0,1,2,3}; 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 12^{m}, and the sum of weights of all other sets of cycle covers is 0, one has Perm(G_{φ}) = 12^{m}·(#φ). The following section reduces computing Perm(G_{ϕ}) to the permanent of a 01 matrix.
01Matrix
The above section has shown that Permanent is #Phard. 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 01Permanent is #Phard as well.
Reduction to a nonnegative matrix
Using modular arithmetic, convert an integer matrix A into an equivalent nonnegative matrix A' so that the permanent of A can be computed easily from the permanent of A', as follows:
Let A 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 P < Q / 2 then Perm(A) = P. Otherwise Perm(A) = P − Q
The transformation of A into A' is polynomial in n and log(μ), since the number of bits required to represent Q is polynomial in n and log(μ)
An example of the transformation and why it works is given below.
 .
Here, n = 2, μ = 2, and μ^{n} = 4, so Q = 17. Thus
Note how the elements are nonnegative because of the modular arithmetic. It is simple to compute the permanent
so . Then P < Q / 2, so
Reduction to powers of 2
Note that any number can be decomposed into a sum of powers of 2. For example,
 13 = 2^{3} + 2^{2} + 2^{0}
This fact is used to convert a nonnegative 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 G be a nnode weighted directed graph with nonnegative weights, where largest weight is W. Every edge e with weight w 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 r nodes and 3r edges.
To prove that this produces an equivalent graph G' that has the same permanent as the original, one must show the correspondence between the cycle covers of G and G'.
Consider some cyclecover R in G.
 If an edge e is not in R, then to cover all the nodes in the new sub graph, one must use the selfloops. Since all selfloops have a weight of 1, the weight of cyclecovers in R and R' match.
 If e is in R, then in all the corresponding cyclecovers in G', there must be a path from u to v, where u and v are the nodes of edge e. From the construction, one can see that there are r different paths and sum of all these paths equal to the weight of the edge in the original graph G. So the weight of corresponding cyclecovers in G and G' match.
Note that the size of G' is polynomial in n and log W.
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 nnode directed graph where all the weights on edges are powers of two. Construct a graph, G', where the weight of each edge is 1 and Perm(G) = Perm(G'). The size of this new graph, G', is polynomial in n and p where the maximal weight of any edge in graph G is 2^{p}.
This reduction is done locally at each edge in G that has a weight larger than 1. Let e = (u,v) be an edge in G with a weight w = 2^{r} > 1. It is replaced by a subgraph J_{e} that is made up of 2r nodes and 6r edges as seen in Figure 2. Each edge in J_{e} has a weight of 1. Thus, the resulting graph G' contains only edges with a weight of 1.
Consider some cyclecover R in G.
 If an original edge e from graph G is not in R, one cannot create a path through the new subgraph J_{e}. The only way to form a cycle cover over J_{e} in such a case is for each node in the subgraph to take its selfloop. 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 G' there must be a path from u to v 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 r times, resulting in 2^{r} possible paths from u to v. Thus, there are 2^{r} 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.
References
 ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science (Elsevier) 8 (2): 189–201. doi:10.1016/03043975(79)900446.
 ^ ^{a} ^{b} Christos H. Papadimitriou. Computational Complexity. AddisonWesley, 1994. ISBN 0201530821. Page 443
 ^ Allen Kent, James G. Williams, Rosalind Kent and Carolyn M. Hall (editors). Encyclopedia of microcomputers.Marcel Dekker, 1999. ISBN 9780824727222; p. 34
 ^ JinYi 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. SpringerVerlag, New York, LLC Pub. Date: October 2007. ISBN 9783540656913; p. 90.
 ^ L. 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, SpringerVerlag, New York, 2007. ISBN 9783540587156; p. 265
 ^ Peter Burgisser.Completeness and Reduction in Algebraic Complexity Theory. SpringerVerlag, New York, 2000. ISBN 9783540667520; p. 2
 ^ John E. Hopcroft, Richard M. Karp: An n^{5 / 2} Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4), 225–231 (1973)
 ^ Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. "26.5: The relabeltofront algorithm". Introduction to Algorithms (2nd ed.). MIT Press and McGrawHill. pp. pp. 696–697. ISBN 0262032937.
 ^ ^{a} ^{b} Dexter Kozen. The Design and Analysis of Algorithms. SpringerVerlag, New York, 1991. ISBN 9780387976877; pp. 141–142
 ^ Seinosuke Toda. PP is as Hard as the PolynomialTime Hierarchy. SIAM Journal on Computing, Volume 20 (1991), Issue 5, pp. 865–877.
 ^ 1998 Gödel Prize. Seinosuke Toda
 ^ W. Hartmann. On the complexity of immanants. Linear and Multilinear Algebra 18 (1985), no. 2, pp. 127–140.
 ^ BenDor, Amir; Halevi, Shai (1993). "Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems". pp. 108–117. http://citeseer.ist.psu.edu/bendor95zeroone.html..
Categories: Computational problems
 Combinatorics
 Article proofs
Wikimedia Foundation. 2010.
Look at other dictionaries:
SharpPcomplete — The correct title of this article is #P complete. The substitution or omission of the # sign is because of technical restrictions. #P complete, pronounced sharp P complete or number P complete is a complexity class in computational complexity… … Wikipedia
SharpP — The correct title of this article is #P. The substitution or omission of the # sign is because of technical restrictions. In computational complexity theory, the complexity class #P (pronounced number P or, sometimes sharp P or hash P ) is the… … Wikipedia
Permanent way — The permanent way means the physical elements of the railway line itself: generally the pairs of rails typically laid on sleepers embedded in ballast, intended to carry the ordinary trains of a railway. This page describes British practice and… … Wikipedia
Класс SharpP — Правильный заголовок этой статьи Класс #P. Он показан некорректно из за технических ограничений. В теории сложности, #P является классом проблем, решением которых является количество успешных, т.е., завершающихся в допускающих состояниях,… … Википедия
List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia
List of rock instrumentals — The following is a list of rock instrumentals, including live performances and drum solos, organized by artist name. 0 9 =3= *Bramfatura =311= * Blizza * Cali Soca * Color ( Transistor ) * Dreamland ( Enlarged to Show Detail 2 ) * Old Funk *… … Wikipedia
china — /chuy neuh/, n. 1. a translucent ceramic material, biscuit fired at a high temperature, its glaze fired at a low temperature. 2. any porcelain ware. 3. plates, cups, saucers, etc., collectively. 4. figurines made of porcelain or ceramic material … Universalium
China — /chuy neuh/, n. 1. People s Republic of, a country in E Asia. 1,221,591,778; 3,691,502 sq. mi. (9,560,990 sq. km). Cap.: Beijing. 2. Republic of. Also called Nationalist China. a republic consisting mainly of the island of Taiwan off the SE coast … Universalium
United Kingdom — a kingdom in NW Europe, consisting of Great Britain and Northern Ireland: formerly comprising Great Britain and Ireland 1801 1922. 58,610,182; 94,242 sq. mi. (244,100 sq. km). Cap.: London. Abbr.: U.K. Official name, United Kingdom of Great… … Universalium
United States — a republic in the N Western Hemisphere comprising 48 conterminous states, the District of Columbia, and Alaska in North America, and Hawaii in the N Pacific. 267,954,767; conterminous United States, 3,022,387 sq. mi. (7,827,982 sq. km); with… … Universalium