ABSTRACT
We already learned in Chapter 1 that #SAT is #P-complete. This chapter provides a comprehensive list of #P-complete counting problems and introduces the main proving techniques. We have to distinguish two different ways to prove #P-completeness. The reason for the distinction is that one of the proving techniques for #P-completeness actually proves more: it also proves that the counting problem does not have an FPRAS unless RP = NP. These proving techniques apply polynomial reductions reducing #SAT to some counting problem #A that keeps the relative error. That is, if the 166computation of problem instances from #A was only approximate, then still separating the zero and non-zero number of solutions of a problem instance from #SAT could be done with high probability. That is, it would provide a BPP algorithm for SAT, which, as we already learned, would imply that RP = NP. Other proving techniques apply polynomial reduction in which at least one operation does not keep the relative error. This might be a subtraction or modulo prime number calculation. Many (but definitely not all) of those computational problems whose #P-completeness is proved in this way are in FPRAS and in FPAUS. Below we detail these proving techniques.
167Polynomial reductions that keep the relative error. These reductions are also called approximation-preserving reductions.
A polynomial reduction that for a CNF Φ, it constructs a problem instance x in #A such that the number of solutions of x is exactly the number of satisfying assignments of Φ. Such reduction actually also proves the NP-completeness of the corresponding decision problem A. Thus, #A does not have an FPRAS unless RP = NP. An example in this chapter is the proof of the #P-completeness of the #3SAT. This type of reduction is also called a parsimonious [155] reduction.
A polynomial reduction that for a CNF Φ, it constructs a problem instance x in some function problem A such that the answer for x is a number which is k times the number of satisfying assignments of Φ, where k can be computed in polynomial time. Typically, the computational problem A is to compute the sum of weights of some discrete mathematical objects, for example, the weights of cycle covers in a directed graph. This happens to coincide with the permanent of the corresponding weighted adjacency graph, as shown in this chapter. Such proof proves neither that deciding if the set of the discrete mathematical objects is not empty is NP-complete nor that finding the minimum or maximum weighted object is NP-hard. However, an FPRAS algorithm for #A would prove that RP = NP.
A polynomial reduction that for a CNF Φ, it constructs a problem instance x in #A such that the number of solutions of x is a + b y https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3439.tif"/> , where 0 ≤ a ≪ b https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3440.tif"/> , y is the number of satisfying assignments of Φ, and b is easy to compute. Such a reduction proves the #P-completeness of #A. Indeed, a + b y b https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3441.tif"/> is the number of satisfying assignments of Φ. It is easy to see that an FPRAS for #A would imply that RP = NP. Examples in this chapter are the proof of #P-completeness of counting the most parsimonious substitution histories on a binary tree and the proof of #P-completeness of counting independent sets in a graph.
Polynomial reductions that do not keep the relative error. Such reductions do not exclude the possibility for an FPRAS approximation; on the other hand, they do not guarantee the existence of efficient approximations.
Reductions using only one subtraction. For example, this is the way to reduce #SAT to #DNF.
Modulo prime number calculations. This is applied in reducing the permanent computation of matrices of − 1 , 0 , 1 , 2 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3442.tif"/> and 3 to matrices containing only small non-negative integers.
Polynomial interpolation. This reduction is based on the following fact. If the value of a polynomial of order n is computed in n + 1 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3443.tif"/> different points, then the coefficients of the polynomial can be determined in polynomial time by solving a linear equation system. In the polynomial reduction, for a problem instance a in the #P-complete problem A, m + 1 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3444.tif"/> problem instances b j https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3445.tif"/> from problem B are constructed such that the number of solutions for b j https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3446.tif"/> is the evaluation of some polynomial ∑ i = 0 m c i x i https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3447.tif"/> at distinct points x = x j https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3448.tif"/> . For some k, c k https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315266954/a85766f8-14e4-4bbb-b5b7-768a0bb107fc/content/eq3449.tif"/> is the number of solutions of problem instance a. This is a very powerful approach that is used in many #P-completeness proofs of counting problems including counting the not necessarily perfect matchings in planar graphs and counting the subtrees of a graph.
Reductions using other linear equation systems. An example in this chapter is the reduction of the number of perfect matchings to the number of Eulerian orientations of a graph.
