Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 9

Complexity of Counting

How do I love thee? Let me count the ways.

I love thee to the depth and breadth and height

My soul can reach.

—Elizabeth Barrett Browning

Informally, the complexity class NP contains the decision problems in which an input instance is accepted if and only if there exists a good witness. The complexity classes PP and BPP contain the problems in which an input instance is accepted if and only if the majority of the witnesses are good. All these problems are just the restricted forms of a more general counting problem: for any input instance, count the number of good witnesses for it. Such counting problems occur very often in practical problems. For instance, for the HAMILTONIAN CIRCUIT problem, one is often interested not only in the existence of a Hamiltonian circuit in a graph but also interested in the total number of different Hamiltonian circuits. In this chapter, we study the complexity of these counting problems and its relation to the complexity of nondeterministic and probabilistic computation. We define two complexity classes, #P and $c09-math-0002$ , of counting problems. The main result of this chapter shows that decision problems in the polynomial-time hierarchy are polynomial-time reducible to counting problems in these complexity classes. We also investigate the relation between the relativized #P and the relativized polynomial-time hierarchy.

9.1 Counting Class $c09-math-0004$

Almost all problems we studied so far are decision problems that for an input x ask for answers of a single bit (i.e., YES or NO). In practice, however, we often encounter search problems that for an input x ask for an output y that may be muchlonger than one bit. We have seen in Chapter 2 how to reduce some search problems, particularly the optimization problems, to the corresponding decision problems. Still complexity classes for decision problems, such as NP and BPP, are not adequate to characterize precisely the complexity of search problems. A particularly interesting class of search problems is the class of counting problems related to nondeterministic computation. A decision problem in NP asks, for each input x, whether there exists a witness (or a solution) to x. The corresponding counting problem asks, for any input x, the number of witnesses for x.

Example 9.1

The above example can be extended to other NP-complete problems such as VERTEX COVER and HAMILTONIAN CIRCUIT. In general, for each NP-complete decision problem, there is a corresponding counting problem that is not polynomial-time solvable if $c09-math-0016$ .

Example 9.2

Recall the problem PERFECT MATCHING (PM) defined in Chapter 6: For a given bipartite graph G, determine whether there exists a perfect matching for G. We define the corresponding counting problem as follows:

$c09-math-0019$ : Given a bipartite graph G, determine the number of perfect matchings there are for G.

It is well known that the decision problem PM is solvable in polynomial time, and it was shown in Theorem 6.49 that PM isin RNC. However, these algorithms for the decision problem of bipartite matching do not seem applicable to the corresponding counting problem $c09-math-0022$ . Indeed, in the next section, we will show that $c09-math-0023$ is as hard as #SAT and is not solvable in polynomial time if $c09-math-0025$ . Therefore, in general, the complexity of a counting problem cannot be characterized precisely from the complexity of the corresponding decision problem.

Formally, a counting problem is a function f mapping an input $c09-math-0027$ to an integer $c09-math-0028$ . The computational model for counting problems is the DTM transducer. A counting problem $c09-math-0029$ is computable if there exists a DTM transducer M such that for each input $c09-math-0031$ , M(x) outputs integer f(x) in the binary form; it is polynomial-time computable if it is computable by a polynomial-time DTM transducer. In other words, a counting problem f is polynomial-time computable if it is in FP. Note that a function $c09-math-0035$ must be polynomially length bounded, that is, for all x, $c09-math-0037$ for some polynomial p. Thus, if a counting problem f is in FP, then $c09-math-0041$ for some polynomial p.

Many counting problems such as #SAT and $c09-math-0044$ can easily be defined in terms of NTMs. For any polynomial-time NTM M, we define a counting problem φ_M as follows: For any $c09-math-0047$ , $c09-math-0048$ is the number of accepting computation paths of M(x). As each computation path of M(x), with $c09-math-0051$ , is of length $c09-math-0052$ for some polynomial p, we have the bounds $c09-math-0054$ , where c is a constant bounding the number of nondeterministic choices of M in a nondeterministic move. Thus, all functions φ_M are polynomial-length bounded. Let $c09-math-0058$ denote the class of all polynomial-time NTMs.

Definition 9.3

It is easy to see that each counting function in FP is also in #P. The fundamental question concerning counting problems is whether $c09-math-0062$ .

Proposition 9.4

Proof

To understand the power of the counting class #P, we first consider its relation with class NP. From the definition of φ_M, it is clear that M accepts x if and only if $c09-math-0081$ . Thus, it follows that $c09-math-0082$ is at least as powerful as NP. Next we consider the relation between $c09-math-0083$ and PP. Assume that $c09-math-0084$ is computed by a polynomial-time PTM M in uniform time t(n), that is, every branch of the computation of M(x) halts in exactly $c09-math-0088$ moves. Define an NTM M₁ that on input x guesses a string y of length $c09-math-0092$ and accepts x if and only if $c09-math-0094$ accepts. Then, it follows that $c09-math-0095$ if and only if $c09-math-0096$ . Thus, $c09-math-0097$ is at least as powerful as PP.

In the following, we formalize these observations in terms of polynomial-time reducibilities to show that the classes $c09-math-0098$ and PP are equivalent under the polynomial-time Turing reducibility. The notions of function-oracle Turing machines and polynomial-time Turing reducibility on functions have been defined in Chapter 2. Recall that a set A is polynomial-time Turing reducible to a function f, written $c09-math-0101$ or $c09-math-0102$ , if there is a polynomial-time function-oracle TM that computes the characteristic function χ_A of A when the function f is used as an oracle. Let $c09-math-0106$ be a class of functions. We let $c09-math-0107$ denote the class of all sets A that are $c09-math-0109$ -reducible to some functions $c09-math-0110$ .

To prepare for this result, we first show that we can restrict $c09-math-0111$ to contain only functions φ_M that correspond to NTMs that run in polynomial time in uniform time complexity.

Proposition 9.5

Proof

It is obvious that (b) $c09-math-0130$ (c) and (b) $c09-math-0131$ (a). We only show (a) $c09-math-0132$ (b): Let M be an NTM with time complexity p(n) for some polynomial p. Assume that M has at most c nondeterministic choices in each move. Let M₁ be the NTM obtained from M with the following modification:

At each nondeterministic move of M, M₁ makes $c09-math-0142$ many nondeterministic moves, creating two computation paths in each move. Thus, each nondeterministic move of M is simulated in M₁ by $c09-math-0145$ computation paths. Among them, let the first c paths simulate the first c paths of M and the rest reject.
Let $c09-math-0149$ be a fully time constructible polynomial function such that $c09-math-0150$ . On any input x of length n, M₁ runs exactly $c09-math-0154$ moves before it halts. (If a computation path enters a halting state of M before that, M₁ keeps the same output for the following moves until it runs exactly $c09-math-0157$ moves.)

It is clear that $c09-math-0158$ has exactly the same number of accepting paths as M(x).

Theorem 9.6

Proof

It is immediate from the definition that a problem A in PP can be easily computed using an oracle function f that counts the number of accepting computations of the PTM for A and then accepts the input if and only if this number is greater than one half of all computations. It follows that $c09-math-0164$ .

Conversely, assume that R is a polynomial-time computable relation such that for each x of length n, $c09-math-0168$ only if $c09-math-0169$ for some polynomial p, and that f(x) counts the number of strings y such that $c09-math-0173$ . For any integer m ≥ 0, let w_m denote its binary expansion. We design in the following a PTM M that accepts $c09-math-0177$ if and only if $c09-math-0178$ . Thus, the function f(x) can be computed by a binary search using $c09-math-0180$ PP as the oracle.

Probabilistic Machine M. On input $c09-math-0182$ , with $c09-math-0183$ , flip a coin to get a random string $c09-math-0184$ of length $c09-math-0185$ . Let $c09-math-0186$ with $c09-math-0187$ and $c09-math-0188$ . Accept the input if and only if [ $c09-math-0189$ and z is among the first $c09-math-0191$ strings of length p(n)] or if [ $c09-math-0193$ and $c09-math-0194$ ].

Note that $c09-math-0195$ , and so $c09-math-0196$ if and only if $c09-math-0197$ .

From the above theorem and Theorem 8.16, we have immediately the following relation between $c09-math-0198$ and the polynomial-time hierarchy.

Corollary 9.7

In Section 9.4, we will extend this result to show that the whole polynomial-time hierarchy is contained in $c09-math-0200$ .

9.2 $c09-math-0201$ -Complete Problems

Similar to the notion of NP-completeness, the notion of $c09-math-0202$ -completeness can be used to characterize precisely the complexity of certain counting problems. In this section, we present some $c09-math-0203$ -complete problems.

Definition 9.8

We establish the first $c09-math-0209$ -complete problem #SAT from the generic reduction of Cook's theorem.

Theorem 9.9

Proof

Let $c09-math-0219$ -SAT be the problem #SAT restricted to 3-CNF Boolean formulas.

Corollary 9.10

Proof

We observe that most reductions used to prove NP-completeness in Section 2.3 either preserve a simple relation between the number of solutions of the two problems or can be easily modified to have this property. Thus, these reductions can be extended into reductions for the corresponding counting problems. In the following, we show that the counting problem for VERTEX COVER is #P-complete. Other #P-complete problems are included in exercises. We let $c09-math-0227$ denote the problem of counting the number of vertex covers of a given size K for a given graph G.

Theorem 9.11

Proof

Recall the reduction from SAT to VC given in the proof of Theorem 2.14. For a 3-CNF formula F of n variables and m clauses, we constructed a graph G_F of $c09-math-0236$ vertices such that F is satisfiable if and only if G_F has a vertex cover of size $c09-math-0239$ . This reduction does not preserve the number of witnesses. In particular, for each Boolean assignment τ for F, there is a unique n-vertex cover X_τ for $c09-math-0244$ . If τ satisfies one out of three literals of a clause C_j, then, with respect to X_τ, there is a unique way to choose two vertices to cover the triangle $c09-math-0248$ . If τ satisfies two out of three literals of C_j, then there are two ways to cover T_j by two vertices. If τ satisfies all three literals of C_j, then there are three ways to cover T_j by two vertices. That is, the number of vertex covers for graph G_F depends not only on the number of satisfying assignments for F but also on the number of literals satisfied in each clause. Therefore, there does not have a simple relation between the numbers of witnesses.

In the following, we make a simple modification of the graph G_F. Our new graph $c09-math-0258$ has the property that the number of vertex covers for $c09-math-0259$ is equal to 4^m times the number of satisfying assignments for F. $c09-math-0262$ contains G_F as a subgraph and contains, for each clause C_j, $c09-math-0265$ , seven additional vertices: $c09-math-0266$ , and d_j,k, e_j,k, $c09-math-0269$ . Assume that the three literals of C_j are $c09-math-0271$ . For each j, $c09-math-0273$ , it also contains the following edges:

$c09-math-0274$ , $c09-math-0275$ (so c_j,ℓ's, with $c09-math-0277$ , form a clique of size 4).
$c09-math-0278$ , $c09-math-0279$ .
$c09-math-0280$ , $c09-math-0281$ , $c09-math-0282$ .

We let G_j denote the subgraph of $c09-math-0284$ that includes vertices $c09-math-0285$ , $c09-math-0286$ , $c09-math-0287$ , and all edges incident on them. Figure 9.1 shows G_j corresponding to the clause $c09-math-0289$ .

It is easy to see that for each G_j, we need at least six vertices to cover it (not including the edges $c09-math-0292$ ). In addition, we verify that for each Boolean assignment τ that satisfies a clause C_j, there are exactly four ways to cover G_j.

Case 1. τ satisfies only one literal of C_j, say, $c09-math-0298$ . Then, the minimum vertex cover must contain $c09-math-0299$ , because each of them is connected to at least one of the unsatisfied literals $c09-math-0300$ or $c09-math-0301$ . In addition, it must contain $c09-math-0302$ , because it is connected to $c09-math-0303$ . For the other two vertices, we could choose one from $c09-math-0304$ and $c09-math-0305$ and one from $c09-math-0306$ and $c09-math-0307$ . So, there are four different ways to cover G_j.

Case 2. τ satisfies two literals of C_j, say, $c09-math-0311$ and $c09-math-0312$ . Using a similar argument, we can see that the minimum cover must contain $c09-math-0313$ , $c09-math-0314$ , $c09-math-0315$ , and $c09-math-0316$ and may contain one from $c09-math-0317$ and $c09-math-0318$ and one from $c09-math-0319$ and $c09-math-0320$ .

Case 3. τ satisfies all three literals of C_j. Then, the minimum cover must contain $c09-math-0323$ , and $c09-math-0324$ . It may choose any three out of four vertices c_j,k, $c09-math-0326$ .

Thus, for each satisfying assignment for F, there are exactly four ways to cover each G_jand, hence, 4^m ways to cover the graph $c09-math-0330$ . This simple relation between the numbers of witnesses of F and $c09-math-0332$ shows that $c09-math-0333$ is #P-complete.

From the above theorem and other similar results (see Exercise 9.1), one might suspect that $c09-math-0335$ -completeness is just a routine extension from NP-complete decision problems to their corresponding counting problems. The following result shows that this is not true: there exist some decision problems in P whose corresponding counting problems are nevertheless $c09-math-0336$ -complete.

We first show that the problem PERM, of computing the permanent of an integer matrix, is $c09-math-0337$ -complete. The permanent of an $c09-math-0338$ integer matrix A is

where S_n is the set of all permutations on $c09-math-0342$ . Note that the determinant of a matrix A has a similar form except that a factor of $c09-math-0344$ is multiplied to each odd permutation. It is well known that determinants of integer matrices are computable in polynomial time (indeed in NC²). However, no polynomial-time algorithms for permanents are known, despite the similarity between the two problems. The $c09-math-0346$ -completeness of the function perm shows that the two problems are really quite different as far as their complexity is concerned (assuming $c09-math-0347$ ).

The problem PERM has a number of equivalent formulation. One of them is the problem $c09-math-0348$ of counting the number of perfect matchings (Example 9.2). Another one is the cycle covering problem. Let $c09-math-0349$ be a directed graph and $c09-math-0350$ a weight function on the edges of G, where $c09-math-0352$ denotes the set of integers. A collection C of node-disjoint cycles that cover all nodes in G is called a cycle cover of G. The weight of a cycle cover C is the product of the weights of all edges in C. The cycle covering problem is the following:

#CC: Given a directed graph G with a weight function w on edges of G, find the sum of the weights of all cycle covers of G.

For any $c09-math-0362$ integer matrix A, define G_A to be the directed graph that has n vertices $c09-math-0366$ and has a weight function $c09-math-0367$ , that is, the adjacency matrix of G_A is A. The following lemma shows a simple relation between the problems $c09-math-0370$ and PERM.

Lemma 9.12

Proof

Theorem 9.13

Proof

Theorem 9.14

Proof

It is easy to see that PERM and #CC are in #P. From the above theorem, it suffices to construct a reduction from #SAT to #CC. For each Boolean formula F as an instance of #SAT, we will construct an edge-weighted-directed graph G such that the sum of the weights of all cycle covers of G is equal to $c09-math-0401$ , where c(F) is the number of clauses in F and s(F) is the number of Boolean assignments that satisfy F. This gives a Turing reduction from #SAT to #CC.

A basic component of the graph G is a junction J, which is a 4-node-directed graph with the following adjacency matrix:

For each junction J, we let $c09-math-0410$ , $c09-math-0411$ , denote the ith node in J.

Let $c09-math-0414$ denote the matrix obtained from X, removing rows $c09-math-0416$ and columns $c09-math-0417$ . Then, the following properties of X are easy to verify:

$c09-math-0419$ ;
$c09-math-0420$ .

These properties on matrix X imply certain interesting properties about cycle covers of J, which will be used later.

We now begin our construction. Let F be a 3-CNF Boolean formula with clauses C₁, $c09-math-0425$ , C_n and variables x₁, $c09-math-0428$ , x_m. The graph G contains the following components:

For each clause C_j and each variable x_i that occurs in C_j (either positively or negatively), define a junction J_i,j that is isomorphic to J defined above.
For each variable x_i, define a track T_i that connects all J_i,j together. Assume that x_i occurs positively inclauses $c09-math-0440$ and negatively in clauses $c09-math-0441$ . Then, T_i contains two nodes u_i and v_i, junctions $c09-math-0445$ , $c09-math-0446$ , with $c09-math-0447$ and $c09-math-0448$ , and the following edges:
Note that, in the above, all edges enter a junction J_i,j from node 1 and leave a junction from node 4. The track T_i is shown in Figure 9.2.
For each clause C_j, define an interchange R_j that connects to some tracks T_i through junctions J_i,j. Assume that the three variables occurring in C_j are $c09-math-0458$ , $c09-math-0459$ , and $c09-math-0460$ . Then the interchange R_j contains nine nodes: p_j, q_j, a_j,k, $c09-math-0465$ , b_j,h, $c09-math-0467$ ; three junctions: $c09-math-0468$ , $c09-math-0469$ ; and the following edges between them:
Note that all edges in R_j enter a junction at node 4 and leave from node 1. We show the interchange R_j in Figure 9.3. In Figure 9.3, all junctions are shown to have node 1 to the right and node 4 to the left.
In the above design, the weight of any edge not in a junction is defined to be 1.

We now observe the following properties of the graph G: First, define a route to be the collection of all cycle covers that have the same set of edges outside the junctions. A route is good if for each junction J in G it enters J exactly once from node 1 or node 4 and leaves J from node 4 or, respectively, node 1. The main idea of the design of matrix X above is to ensure that all bad routes together contribute weight 0 to the total weight. Let Q be a route. We write w(Q) to denote the sum of weights of all cycle covers in Q.

Claim 1. A route Q that is not good has weight 0.

Proof

A route Q is not good if one of the following holds:

It never enters a junction J;
It enters a junction J exactly once from node 1 and leaves from node 1;
It enters a junction J exactly once from node 4 and leaves from node 4; or
It enters a junction J twice.

In each case, the corresponding local cycles that cover the junction J contribute weight 0 to the weight of Q, as shown in property (i) of matrix X. For instance, suppose that Q is bad because of (b) above. Then all cycle covers in Q leave nodes 2, 3, and 4 of junction J to be covered by local cycles. Let Q₁ be the set of cycle covers of nodes 2, 3, and 4 of J. Let G₁ be the graph G with nodes 2, 3, and 4 of junction J removed. For any cycle cover D₁ of G₁, we have

As each cycle cover D in Q must contain a cycle cover D₁ for G₁, it follows that the weight of Q is 0. Other cases can be verified similarly.

Claim 2. A good route Q has weight $c09-math-0509$ .

Proof

Claim 3. Each interchange R_j has the following properties:

There is no good route for R_j.
Let $c09-math-0537$ be R_j with at least one of $c09-math-0539$ removed, $c09-math-0540$ . Then, there is a unique good route for $c09-math-0541$ .

Proof

The following claim finishes the proof of the theorem.

Claim 4. There are exactly s(F) good routes for G.

Proof

Now we apply the above result to show that the perfect matching problem is $c09-math-0598$ -complete. As the problem of determining whether a given bipartite graph G has a perfect matching is polynomial-time solvable, this result demonstrates the first $c09-math-0600$ -complete problem whose corresponding decision problem is in P.

Let $c09-math-0601$ be a bipartite graph in which $c09-math-0602$ . Define an $c09-math-0603$ (0,1)-matrix M_G as follows:

Then, it is clear that $c09-math-0606$ is exactly the number of perfect matchings in G. Thus, it suffices to prove that the problem of computing the permanents of $c09-math-0608$ -matrices is $c09-math-0609$ -complete.

Theorem 9.15

Proof

We first prove that the problem of computing $c09-math-0612$ for any given $c09-math-0613$ integer matrix A and any prime $c09-math-0615$ is #P-complete. In Theorem 9.14, we have proved that the problem of computing $c09-math-0617$ is #P-complete if A is an integer matrix with values in $c09-math-0620$ . Note that for such matrices A, $c09-math-0622$ . From the prime number theorem, for sufficiently large n, the product of all primes less than n² is greater than $c09-math-0625$ . By the Chinese remainder theorem, $c09-math-0626$ could be found, in polynomial time, from $c09-math-0627$ , for primes $c09-math-0628$ (see, e.g., Knuth (1981), Section 4.3.2). Therefore, the problem of computing $c09-math-0629$ is reduced to the problem of computing $c09-math-0630$ , $c09-math-0631$ .

Next, we reduce the problem of computing $c09-math-0632$ to the problem of computing $c09-math-0633$ for $c09-math-0634$ -matrices B. We recall the translation of Theorem 9.13 between the permanent problem and the weighted cycle covering problem. Let G_A be the directed graph whose adjacency matrix is equal to A. As we are only interested in $c09-math-0638$ , we may assume that all weights in G_A are in $c09-math-0640$ . For each edge (u,v) in G_A that has a weight $c09-math-0643$ , we replace it by a graph H_k as follows:

The graph H_k has $c09-math-0646$ nodes

and $c09-math-0648$ edges

Each edge of H_k has the weight 1. We show the graph H_k in Figure 9.4.

Assume that in a graph G, an edge (u,v) of weight k is replaced by H_k to form a new graph $c09-math-0657$ . Then, for any cycle cover C of G that does not include (u,v), there is exactly one cycle cover C^′ of G^′ that has all the edges of C plus a unique cycle cover for $c09-math-0664$ . For any cycle cover C of G that includes (u,v), there are k cycle covers C₁, $c09-math-0670$ , C_k of G^′ that contain $c09-math-0673$ plus the path $c09-math-0674$ and a cycle cover of $c09-math-0675$ . Thus, $c09-math-0676$ .

Therefore, replacing each edge of weight k in G by a graph H_k creates a new graph G₁ such that G₁ contains only edges of weight 1 or 0 and $c09-math-0682$ . This completes the proof.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter

Create new playlist

Sign In

Sign Up

Complexity of Counting

9.1 Counting Class

Example 9.1

Example 9.2

Definition 9.3

Proposition 9.4

Proof

Proposition 9.5

Proof

Theorem 9.6

Proof

Corollary 9.7

9.2 -Complete Problems

Definition 9.8

Theorem 9.9

Proof

Corollary 9.10

Proof

Theorem 9.11

Proof

Lemma 9.12

Proof

Theorem 9.13

Proof

Theorem 9.14

Proof

Proof

Proof

Proof

Proof

Theorem 9.15

Proof

Table of Contents for
Chapter

9.1 Counting Class $c09-math-0004$

9.2 $c09-math-0201$ -Complete Problems