Corollary 9.27

Corollary 9.31

Proof

9.5 Circuit Complexity and Relativized and

We have seen in the last two sections that the class is hard for PH under the polynomial-time randomized reduction and the class is hard for PH under the polynomial-time Turing reduction. These results imply that if or is actually contained in PH, then PH collapses into a finite hierarchy. On the other hand, if either or is provably not contained in PH, then , because . Therefore, it appears difficult to determine the precise relations between, , and the polynomial-time hierarchy.

In this section, we investigate the relativized relations between these counting complexity classes and the polynomial-time hierarchy. We prove that in the relativized form, the complexity classes and are not contained in PH. The proof technique is particularly interesting, as it demonstrates a simple relation between the relativized separation results on classes in PH and the lower bound results on circuit complexity. Using the lower bound results on constant-depth circuits of Section 6.6, we are able to separate the relativized counting complexity classes from the polynomial-time hierarchy and, moreover, to separate the polynomial-time hierarchy into a properly infinite hierarchy by oracles.

We first show how to translate a relativized separation problem involving the polynomial-time hierarchy into a lower bound problem about constant-depth circuits. Recall from Chapter 3 a set B in can be characterized by a -predicate : for each x of length n,

9.3

where Q_k is if k is odd and is if k is even and R is a polynomial-time computable predicate relative to any oracle A. Also recall from Section 6.6 the notion of constant-depth levelable Boolean circuits. Such a circuit has alternating AND and OR gates at each level. Each gate of the circuit has an unlimited fan-in, and its input nodes can take an input value as it is or take its negated value. In the following, by a circuit we mean a constant-depth levelable circuit. We label each input node of a circuit C by a string z or its negation . These labels are called variables of C. We say that a variable z in C is assigned with a Boolean value b to mean that each input node with the label z takes the input value b and each input node with the label takes the input value .

Theorem 9.37

Proof

Finally, we remark that it is unknown whether the relativized polynomial-time hierarchy is a properly infinite hierarchy relative to a random oracle. In Theorem 9.35, we applied the stronger lower bound result on parity circuits to show that is not contained in PH^A relative to a random oracle A. Namely, the stronger lower bound implies that no circuit of a constant depth d and size for any polynomial p can approximate the parity function correct on more than inputs. Similarly, if we could show a stronger lower bound result on depth- Circuits that -approximate , then it follows that the polynomial-time hierarchy is properly infinite relative to a random oracle. Note, however, that the symmetry property of the parity function is critical to the proof of Theorem 9.34. Without the symmetry property, the lower bound on the approximation circuits for function appears more difficult.

Exercises

9.1 Let be the problem of counting the number of Hamiltonian circuits of a given graph G and #SS be the problem of counting the number of ways to select a sublist, from a given list of integers, so that the sublist sums to a given integer K > 0. Prove that the problems and #SS are -complete.

9.2 A matching in a bipartite graph G is a set of edges which do not share common vertices. The problem GENERAL MATCHING (GM) is to count the number of matchings of a given bipartite graph. Prove that the problem GM is -complete.

9.3 Prove that the problem #SAT remains -complete even if we restrict the input formulas to be of the form 2-CNF and be monotone. (A CNF Boolean formula is monotone if all literals in each clause appear in the nonnegated form.)

9.4 Let LE be the problem of counting the number of linear extensions of a given partial ordering on a given set A; that is, for a given set and a set of ordered pairs of elements in A, find the number of total ordering over A such that for each pair in B, . Prove that the problem LE is -complete. [Hint: Similar to the problem PERM, first show that for each fixed but sufficiently large prime number p, each Boolean formula F can be reduced to a partial ordering P_F on a set A such that #SAT is reducible to the number of linear extensions of P_F.]

9.5 For a set and a subset , a pair (T,a), with and , is said to be consistent with B if [a = 0 and ] or [a = 1 and ].

1. Prove that the following counting problem is #P-complete: for a given set and a set , with and each for each , find the number of subsets such that each pair , , is consistent with B.
2. Prove that the above counting problem remains #P-complete if we only count the number of subsets B of A, which are of size d and consistent with all pairs in X, where is an additional input parameter.

9.6 In the proof of Lemma 9.23, we used the second Swapping Lemma to prove (9.1). This seems unnecessary: By Lemma 9.22(a), the error probability of (9.2) can be reduced to , and then the inequality (9.1), with , follows immediately. Discuss what was wrong with this simpler argument.

9.7 Let n ≥ 1. Identify the set with the vector space of all n-dimensional vectors over the field . Then, for any two strings , their inner product is , where u_i denotes the ith bit of u and denotes the exclusive-or, or the odd parity, operation.

1. For any random strings w₁, , , define , for . Prove that and .
2. Let S be a nonempty subset of . For any random strings w₁, , , define, , . Prove that .
3. Apply part (b) above, instead of the Isolation Lemma, to prove Theorem 9.24.

9.8 Let PRIMESAT = SAT: the number of truth assignments t that satisfies F is a prime number}. Prove that SAT(PRIMESAT).

9.9 In this exercise, we prove a straight-line program characterization of the class #P. A straight-line arithmetic program (or, simply, program) is a finite sequence of instructions such that each p_k, , is of one of the following forms:

1. p_k is a constant 0 or 1,
2. or for some ,
3. for some ,
4. for some , or
5. or for some . ( means the polynomial obtained from p_j by substituting 0 for the variable x_i.)

Such a program is said to compute the polynomial p_t; we denote it by . A family of programs is a uniform family if each has at most k variables and if there is a polynomial-time DTM transducer that prints the instructions of program Q_k from input 1^k. Prove that a counting function is in #P if and only if there is a uniform family of programs Q_k such that, for all of length n, , where w_j denotes the jth bit of w.

9.10 Let be two counting functions, and an integer function. We say that function g approximates f with errors bounded by r(n) if for any ,

1. Let denote the class of functions that are computable by a polynomial-time oracle DTM with respect to an oracle in . Prove that for any and any polynomial function r, there exists a function such that g approximates f with errors bounded by r. In addition, the oracle DTM for g queries only the oracle for at most times.
2. Let denote the class of functions that are computable by a polynomial-time oracle PTM with respect to an oracle in NP such that the error probability is bounded by 1/4. Prove that for any and any polynomial function r, there exists a function such that g approximates f with errors bounded by r. In fact, the oraclemachine for g queries only the oracle for at most times.

9.11 A fully probabilistic polynomial-time approximation scheme for a counting function is a PTM that on inputs x and ε computes, in time polynomial in and with probability 3/4, an approximate value to f(x) with errors bounded by ε.

1. We say a bipartite graph with is dense if each node has degree at least . A 0-1-matrix is called dense if it is the adjacency matrix of a dense bipartite graph. Prove that the problem PERM restricted to dense 0-1-matrices remains #P-complete.
2. Prove that there is a fully probabilistic polynomial-time approximation scheme for computing the permanents of dense 0-1-matrices.

9.12 Prove that the class is closed under the Boolean operations union, intersection, and complementation.

9.13 Let FewP denote the class of languages L that are accepted by polynomial-time NTMs that have at most a polynomial number of accepting computation paths for any . Prove that the class .

9.14 Prove that there exists an oracle A such that and NP^A are incomparable.

9.15 Prove Theorem 9.34. That is, do a more careful analysis of the proofs of Theorems 6.46 and 6.47 to get an exponential lower bound for the size of any depth-d circuit -approximating the parity function p_n.

9.16 Prove Theorem 9.37. In particular, prove that

1. for each integer k > 0, there exists a set A_k such that ; and
2. for each integer k > 0, there exists a set B_k such that . [Hint: Use Exercise 6.21.]

9.17

1. Prove that there exists an oracle C such that for all k ≥ 1.
2. Prove that there exists an oracle D such that for all k ≥ 1.

9.18 In this exercise, we consider the low and high hierarchies in NP. For each k ≥ 0, let be the class of sets such that and be the class of sets such that .

1. Show that and for all k ≥ 0.
2. Show that and equals the class of sets A that are -complete for NP.
3. Show that, for any k ≥ 0, if , then .
4. Show that, for any k ≥ 0, if , then .

9.19 We consider the relativized low and high hierarchies in NP. For any set X, we let denote the class of sets such that and let denote the class of sets such that . Note that Theorem 4.20(c) showed that there exists an oracle A such that .

1. Show that there existsan oracle X such that and for all k ≥ 0.
2. Show that, for any k ≥ 0, there exists an oracle Y such that
3. 
4. and
   
5. Recall the class UP defined in Chapter 4. For k ≥ 0 and any set Z, let . Show that there exists an oracle Z such that UP^Z is not contained in the low and high hierarchies relative to Z, that is,
   

Historical Notes

The class was first defined in Valiant (1979a, 1979b), in which the -completeness of PERM and other counting problems associated with NP-complete problems are proven. The natural reductions among many NP-complete problems are known to preserve the number of solutions; see, for example, Simon (1975) and Berman and Hartmanis (1977). The -completeness of the problem LE (Exercise 9.4) is proved by Brightwell and Winkler (1991). Exercise 9.5 is from Du and Ko (1987). The straight-line program characterization of #P (Exercise 9.9) is from Babai and Fortnow (1991). Papadimitirou and Zachos (1983) studied the class and proved that . Exercise 9.13 is from Cai and Hemachandra (1990). Theorem 9.24 was first proved by Valiant and Vazirani (1986), using a different probabilistic lemma (see Exercise 9.7). The use of the Isolation Lemma simplifies the proof; this was pointed out by Mulmuley et al. (1987). Lemma 9.23, Theorem 9.26, and the results of Section 9.4 are all from Toda (1991). Approximation to counting functions were studied by Stockmeyer (1985), Jerrum et al. (1986), Broder (1986), and Jerrum and Sinclair (1989). Exercises 9.10 and 9.11 are from these works.

The reduction from the relativization problem to the lower bound problem for constant-depth circuits was given in Furst et al. (1984) and Sipser (1983a). They also proved that the parity circuit complexity is super-polynomial. The separation of PSPACE from PH by oracles and the separation of PH into a properly infinite hierarchy by oracles are given in Yao (1985) and Hastad (1986a, 1986b). The collapsing of PH to any finite levels and the separation of PSPACE from a collapsed PH by oracles was proved in Ko (1989a). Theorem 9.35, showing that random oracles separate PSPACE from PH, was first proven by Cai (1986). Our simplified version is from Babai (1987). The low and high hierarchies were first introduced by Schöning (1983). Exercise 9.18 is from there. The relativized separation and collapsing of the low and high hierarchies (Exercise 9.19) was proved by Ko (1991b) and Sheu and Long (1992). Ko (1989b) contains a survey of the proof techniques that use the lower bound results for circuits to construct oracles.