CS254 Lecture 8 – Approximate Counting

Counting Problems

Today we describe counting problems and the class ${{\bf \#P}}$ that they define, and we show that every counting problem ${{\bf \#P}}$ can be approximately solved in randomized polynomial given access to an ${{\bf NP}}$ oracle.

1. Counting Classes

[Note: we did not cover most of the material of this section in class.]

Recall that ${R}$ is an NP-relation, if there is a polynomial time algorithm ${A}$ such that ${(x,y) \in R \Leftrightarrow A(x,y)=1}$ and there is a polynomial ${p}$ such that ${(x,y) \in R \Rightarrow |y| \leq p(|x|)}$ .

Definition 1 If ${R}$ is an ${{\bf NP}}$ relation, then ${\#R}$ is the problem that, given ${x}$ , asks how many ${y}$ satisfy ${(x,y) \in R}$ .

${{\bf \#P}}$ is the class of all problems of the form ${\#R}$ , where ${R}$ is an NP-relation.

Observe that an NP-relation ${R}$ naturally defines an ${{\bf NP}}$ language ${L_R}$ , where ${L_R = \{ x : \exists y. (x,y) \in R \}}$ , and every ${{\bf NP}}$ language can be defined in this way. Therefore problems in ${{\bf \#P}}$ can always be seen as the problem of counting the number of witnesses for a given instance of an ${{\bf NP}}$ problem.

Unlike for decision problems there is no canonical way to define reductions for counting classes. There are two common definitions.

Definition 2 We say there is a parsimonious reduction from ${\#A}$ to ${\#B}$ (written ${\#A \leq_{\text{par}} \#B}$ ) if there is a polynomial time transformation ${f}$ such that for all ${x}$ , ${|\{y,(x,y)\in A \}| = |\{z:(f(x),z)\in B\}|}$ .

Often this definition is a little too restrictive and we use the following definition instead.

Definition 3 ${\#A \leq \#B}$ if there is a polynomial time algorithm for ${\#A}$ given an oracle that solves ${\#B}$ .

${\#CIRCUITSAT}$ is the problem where given a circuit, we want to count the number of inputs that make the circuit output 1.

Theorem 4 ${\#CIRCUITSAT}$ is ${{\bf \#P}}$ -complete under parsimonious reductions.

Proof: Let ${\#R}$ be in ${{\bf \#P}}$ and ${A}$ and ${p}$ be as in the definition. Given ${x}$ we want to construct a circuit ${C}$ such that ${|\{z:C(z)\}| = |\{y:|y|\leq p(|x|), A(x,y)=1\}|}$ . We then construct ${\hat{C}_n}$ that on input ${x,y}$ simulates ${A(x,y)}$ . From earlier arguments we know that this can be done with a circuit with size about the square of the running time of ${A}$ . Thus ${\hat{C}_n}$ will have size polynomial in the running time of ${A}$ and so polynomial in ${x}$ . Then let ${C(y) = \hat{C}(x,y)}$ . $\Box$

Theorem 5 ${\#3SAT}$ is ${{\bf \#P}}$ -complete.

Proof: We show that there is a parsimonious reduction from ${\#CIRCUITSAT}$ to ${\#3SAT}$ . That is, given a circuit ${C}$ we construct a Boolean formula ${\phi}$ such that the number of satisfying assignments for ${\phi}$ is equal to the number of inputs for which ${C}$ outputs 1. Suppose ${C}$ has inputs ${x_1,\ldots,x_n}$ and gates ${1,\ldots,m}$ and ${\phi}$ has inputs ${x_1,\ldots,x_n,g_1,\ldots,g_m}$ , where the ${g_i}$ represent the output of gate ${i}$ . Now each gate has two input variables and one output variable. Thus a gate can be complete described by mimicking the output for each of the 4 possible inputs. Thus each gate can be simulated using at most 4 clauses. In this way we have reduced ${C}$ to a formula ${\phi}$ with ${n+m}$ variables and ${4m}$ clauses. So there is a parsimonious reduction from ${\#CIRCUITSAT}$ to ${\#3SAT}$ . $\Box$

Notice that if a counting problem ${\#R}$ is ${{\bf \#P}}$ -complete under parsimonious reductions, then the associated language ${L_R}$ is NP-complete, because ${\#3SAT \leq_{par} \#R}$ implies ${3SAT \leq L_R}$ . On the other hand, with the less restrictive definition of reducibility, even some counting problems whose decision version is in P are ${{\bf \#P}}$ -complete. For example, the problem of counting the number of satisfying assignments for a given 2CNF formula and the problem of counting the number of perfect matchings in a given bipartite graphs are both ${{\bf \#P}}$ -complete.

2. Complexity of counting problems

We will prove the following theorem:

Theorem 6 For every counting problem ${\#\mbox{A}}$ in ${{\bf \#P}}$ , there is a probabilistic algorithm ${C}$ that on input ${x}$ , computes with high probability a value ${v}$ such that

$\displaystyle (1-\epsilon)\#A(x) \leq v \leq (1+\epsilon)\#A(x) \ \ \ \ \ (1)$

in time polynomial in ${|x|}$ and in ${\tfrac{1}{\epsilon}}$ , using an oracle for ${{\bf NP}}$ .

The theorem says that ${{\bf \#P}}$ can be approximate in ${{\bf BPP}^{{\bf NP}}}$ . We remark that approximating ${\#3SAT}$ is ${{\bf NP}}$ -hard, and so to compute an approximation we need at least the power of ${{\bf NP}}$ . Theorem 6 states that the power of ${{\bf NP}}$ and randomization is sufficient.

Another remark concerns the following result.

Theorem 7 (Toda) For every ${k}$ , ${\Sigma_k \subseteq {\bf P}^{{\bf \#P}}}$ .

This implies that ${\#3SAT}$ is ${\Sigma_k}$ -hard for every ${k}$ , i.e., ${\#3SAT}$ lies outside the polynomial hierarchy, unless the hierarchy collapses. Recall that ${{\bf BPP}}$ lies inside ${\Sigma_2}$ , and hence approximating ${\#3SAT}$ can be done in ${\Sigma_3}$ . Therefore, approximating ${\#3SAT}$ cannot be equivalent to computing ${\#3SAT}$ exactly, unless the polynomial hierarchy collapses.\footnote{The above discussion was not very rigorous but it can be correctly formalized. In particular: (i) from the fact that ${{\bf BPP} \subseteq \Sigma_2}$ and that approximate counting is doable in ${{\bf BPP}^{{\bf NP}}}$ it does not necessarily follow that approximate counting is in ${\Sigma_3}$ , although in this case it does because the proof that ${{\bf BPP} \subseteq \Sigma_2}$ relativizes; (ii) we have defined ${{\bf BPP}}$ , ${\Sigma_3}$ , etc., as classes of decision problems, while approximate counting is not a decision problem (it can be shown, however, to be equivalent to a “promise problem,” and the inclusion ${{\bf BPP} \subseteq \Sigma_2}$ holds also for promise problems.}

We first make some observations so that we can reduce the proof to the task of proving a simpler statement.

It is enough to prove the theorem for ${\#3SAT}$ .
If we have an approximation algorithm for ${\#3SAT}$ , we can extend it to any ${\#\mbox{A}}$ in ${{\bf \#P}}$ using the parsimonious reduction from ${\#\mbox{A}}$ to ${\#3SAT}$ .
It is enough to give a polynomial time ${O(1)}$ -approximation for ${\#3SAT}$ .
Suppose we have an algorithm ${C}$ and a constant ${c}$ such that

$\displaystyle \frac{1}{c}\#3SAT(\varphi)\leq C(\varphi) \leq c\#3SAT(\varphi). \ \ \ \ \ (2)$

Given ${\varphi}$ , we can construct ${\varphi^k=\varphi_1\wedge \varphi_2 \wedge \cdots \wedge \varphi_k}$ where each ${\phi_i}$ is a copy of ${\phi}$ constructed using fresh variables. If ${\varphi}$ has ${t}$ satisfying assignments, ${\varphi^k}$ has ${t^k}$ satisfying assignments. Then, giving ${\varphi^k}$ to the algorithm we get

$\displaystyle \begin{aligned} \frac{1}{c}t^k & \leq C(\varphi^k) \leq c t^k \\ \frac{1}{c}^{1/k}t & \leq C(\varphi^k)^{1/k}\leq {c}^{1/k} t. \end{aligned}$

If ${c}$ is a constant and ${k=O(\frac{1}{\epsilon})}$ , ${{c}^{1/k}=1+\epsilon}$ .
For a formula ${\varphi}$ that has ${O(1)}$ satisfying assignments, ${\#3SAT(\varphi)}$ can be found in ${{\bf P}^{{\bf NP}}}$ .
This can be done by iteratively asking the oracle the questions of the form: “Are there ${k}$ assignments satisfying this formula?” Notice that these are ${{\bf NP}}$ questions, because the algorithm can guess these ${k}$ assignments and check them.

3. An approximate comparison procedure

Suppose that we had available an approximate comparison procedure a-comp with the following properties:

If ${\#3SAT(\varphi)\geq 2^{k+1}}$ then ${{\it a-comp}(\varphi,k)=\text{YES}}$ with high probability;
If ${\#3SAT(\varphi)< 2^{k}}$ then ${{\it a-comp}(\varphi,k)=\text{NO}}$ with high probability.

Given a-comp, we can construct an algorithm that ${2}$ -approximates ${\#3SAT}$ as described below:

Input: ${\varphi}$
compute:
- ${\text{\it a-comp}(\varphi,0)}$
- ${\text{\it a-comp}(\varphi,1)}$
- ${\text{\it a-comp}(\varphi,2)}$
- ${\vdots}$
- ${\text{\it a-comp}(\varphi,n+1)}$
if outputs NO from the first time then
- // The value is either ${0}$ or ${1}$ and the answer can be checked by one more query to the ${{\bf NP}}$ oracle.
- Query to the oracle and output an exact value.
else
- Suppose that it outputs YES for ${t=1,\ldots,i-1}$ and NO for ${t=i}$
- Output ${2^i}$

We need to show that this algorithm approximates ${\#3SAT}$ within a factor of ${2}$ . If a-comp answers NO from the first time, the algorithm outputs the right answer because it checks for the answer explicitly. Now suppose a-comp says YES for all ${t=1,2,\ldots,i-1}$ and says NO for ${t=i}$ . Since ${\text{\it a-comp}(\varphi,i-1)}$ outputs YES, ${\#3SAT(\varphi)\geq 2^{i-1}}$ , and also since ${\text{\it a-comp}(\varphi,2^{i})}$ outputs NO, ${\#3SAT(\varphi)< 2^{i+1}}$ . The algorithm outputs ${a=2^{i}}$ . Hence,

$\displaystyle \frac{1}{2}a\leq \#3SAT(\varphi) < 2\cdot a \ \ \ \ \ (3)$

and the algorithm outputs the correct answer with in a factor of ${2}$ .

Thus, to establish the theorem, it is enough to give a ${{\bf BPP}^{{\bf NP}}}$ implementation of the a-comp procedure

4. Constructing a-comp

The procedure and its analysis is similar to the Valiant-Vazirani reduction: for a given formula ${\phi}$ we pick a hash function ${h}$ from a pairwise independent family, and look at the number of assignments ${x}$ that satisfy ${h}$ and such that ${h(x)={\bf 0}}$ .

In the Valiant-Vazirani reduction, we proved that if ${S}$ is a set of size approximately equal to the size of the range of ${h()}$ , then, with constant probability, exactly one element of ${S}$ is mapped by ${h()}$ into ${\bf 0}$ . Now we use a different result, a simplified version of the “Leftover Hash Lemma” proved by Impagliazzo, Levin, and Luby in 1989, that says that if ${S}$ is sufficiently larger than the range of ${h()}$ then the number of elements of ${S}$ mapped into ${\bf 0}$ is concentrated around its expectation.

Lemma 8 Let ${H}$ be a family of pairwise independent hash functions ${h \: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m}$ . Let ${S\subset \{ 0,1 \}^n}$ , ${|S|\geq \tfrac{4\cdot 2^m}{\epsilon^2}}$ . Then,

$\displaystyle \mathop{\mathbb P}_{h\in H} \left[\left| | \{ a\in S: h(a)=0 \} | -\frac{\|S|}{2^m}\right| \geq \epsilon\frac{|S|}{2^m}\right] \leq \frac{1}{4}. \ \ \ \ \ (4)$

From this, a-comp can be constructed as follows.

input: ${\varphi,k}$
if ${k\leq 5}$ then check exactly whether ${\#3SAT(\varphi)\geq 2^k}$ .
if
- pick ${h}$ from a set of pairwise independent hash functions ${h : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^{m}}$ , where ${m=k-5}$
- answer YES iff there are more then ${48}$ assignments ${a}$ to ${\varphi}$ such that ${a}$ satisfies ${\varphi}$ and ${h(a)=0}$ .

Notice that the test at the last step can be done with one access to an oracle to ${{\bf NP}}$ . We will show that the algorithm is in ${{\bf BPP}^{{\bf NP}}}$ . Let ${S\subseteq \{0,1\}^n}$ be the set of satisfying assignments for ${\varphi}$ . There are 2 cases.

If ${|S|\geq 2^{k+1}}$ , by Lemma 8 we have:
$\displaystyle \mathop{\mathbb P}_{h\in H} \left[\left| \frac{ |S| }{2^m} - | \{a\in S: h(a)=0 \} | \right| \leq \frac{1}{4}\cdot \frac{ |S| }{2^m}\right] \geq \frac{3}{4}$

(set ${\epsilon=\tfrac{1}{4}}$ , and ${ |S| \geq \tfrac{4\cdot 2^m}{\epsilon^2}=64\cdot 2^m}$ , because ${ |S| \geq 2^{k+1} = 2^{m+6}}$ )

$\displaystyle \begin{aligned} \mathop{\mathbb P}_{h\in H} \left[ | \{ a\in S: h(a)=0 \} | \geq \frac 34 \cdot \frac{ |S| }{2^m}\right] & \geq \frac{3}{4},\\ \mathop{\mathbb P}_{h\in H} \left[ | \{a\in S: h(a)=0 \} | \geq 48 \right] & \geq \frac{3}{4},\\ \end{aligned}$

which is the success probability of the algorithm.
If ${|S| < 2^k}$ :
Let ${S'}$ be a superset of ${S}$ of size ${2^k}$ . We have

$\displaystyle \begin{aligned} \mathop{\mathbb P}_{h\in H} [\text{answer YES}] & = \mathop{\mathbb P}_{h\in H} [| \{a\in S : h(s)=0\} | \geq 48]\\ & \leq \mathop{\mathbb P}_{h\in H} [| \{ a\in S' : h(s)=0\} | \geq 48]\\ & \leq \mathop{\mathbb P}_{h\in H} \left[\left| | \{a\in S' : h(s)=0\} |-\tfrac{|S'|}{2^m}\right| \geq\tfrac{| S' | }{2\cdot 2^m}\right]\\ & \leq \frac{1}{4} \end{aligned}$

(by Lemma 8 with ${\epsilon=1/2, |S'|=32\cdot2^m}$ .)

Therefore, the algorithm will give the correct answer with probability at least ${3/4}$ , which can then be amplified to, say, ${1-1/4n}$ (so that all ${n}$ invocations of a-comp are likely to be correct) by repeating the procedure ${O(\log n)}$ times and taking the majority answer.

5. The Remaining Proof

We finish the lecture by proving Lemma 8.

Proof: We will use Chebyshev’s Inequality to bound the failure probability. Let ${S=\{a_1,\ldots,a_k\}}$ , and pick a random ${h\in H}$ . We define random variables ${X_1,\ldots,X_k}$ as

$\displaystyle X_i=\left\{ \begin{aligned} 1 & \text{ if } h(a_i)=0 \\ 0 & \text{ otherwise.} \end{aligned} \right. \ \ \ \ \ (5)$

Clearly, ${| \{ a\in S: h(a)=0 \} | =\sum_i X_i}$ .

We now calculate the expectations. For each ${i}$ , ${\mathop{\mathbb P}[X_i=1]=\tfrac{1}{2^m}}$ and ${\mathop{\mathbb E}[X_i]=\tfrac{1}{2^m}}$ . Hence,

$\displaystyle \mathop{\mathbb E}\left[\sum_i X_i\right]= \frac{ |S| }{2^m}. \ \ \ \ \ (6)$

Also we calculate the variance

$\displaystyle \begin{aligned} \mathop{\bf E}[X_i] & = \mathop{\mathbb E}[X_i^2]-\mathop{\mathbb E}[X_i]^2 \\ & \leq \mathop{\mathbb E}[X_i^2] \\ & = \mathop{\mathbb E}[X_i]= \frac{1}{2^m}. \end{aligned}$

Because ${X_1,\ldots,X_k}$ are pairwise independent,

$\displaystyle \mathop{\bf E}\left[\sum_i X_i\right]=\sum_i \mathop{\bf E}[X_i] \leq \frac{ |S| }{2^m}. \ \ \ \ \ (7)$

Using Chebyshev’s Inequality, we get

$\displaystyle \begin{aligned} \mathop{\mathbb P}\left[\left| | \{ a\in S: h(a)=0 \} | - \frac{ |S| }{2^m}\right| \geq \epsilon \frac{ |S| }{2^m}\right] & = \mathop{\mathbb P}\left[\left|\sum_i X_i - \mathop{\mathbb E}[\sum_i X_i]\right| \geq \epsilon \mathop{\mathbb E}[\sum_i X_i]\right] \\ & \leq \frac{\mathop{\bf E}[\sum_i X_i]}{\epsilon^2 \mathop{\mathbb E}[\sum_i X_i]^2} \leq \frac{ \frac{ |S| }{2^m}}{\epsilon^2 \frac{ |S| ^2}{(2^m)^2}} \\ & = \frac{2^m}{\epsilon^2 |S| } \leq \frac{1}{4}. \end{aligned}$

$\Box$

6. Approximate Sampling

The content of this section was not covered in class; it’s here as bonus material. It’s good stuff.

So far we have considered the following question: for an NP-relation ${R}$ , given an input ${x}$ , what is the size of the set ${R_x = \{ y : (x,y)\in R\}}$ ? A related question is to be able to sample from the uniform distribution over ${R_x}$ .

Whenever the relation ${R}$ is “downward self reducible” (a technical condition that we won’t define formally), it is possible to prove that there is a probabilistic algorithm running in time polynomial in ${|x|}$ and ${1/\epsilon}$ to approximate within ${1+\epsilon}$ the value ${|R_x|}$ if and only if there is a probabilistic algorithm running in time polynomial in ${|x|}$ and ${1/\epsilon}$ that samples a distribution ${\epsilon}$ -close to the uniform distribution over ${R_x}$ .

We show how the above result applies to 3SAT (the general result uses the same proof idea). For a formula ${\phi}$ , a variable ${x}$ and a bit ${b}$ , let us define by ${\phi_{x \leftarrow b}}$ the formula obtained by substituting the value ${b}$ in place of ${x}$ .\footnote{ Specifically, ${\phi_{x \leftarrow 1}}$ is obtained by removing each occurrence of ${\neg x}$ from the clauses where it occurs, and removing all the clauses that contain an occurrence of ${x}$ ; the formula ${\phi_{x \leftarrow 0}}$ is similarly obtained.}

If ${\phi}$ is defined over variables ${x_1,\ldots,x_n}$ , it is easy to see that

$\displaystyle \#\phi = \#\phi_{x \leftarrow 0} + \#\phi_{x \leftarrow 1}$

Also, if ${S}$ is the uniform distribution over satisfying assignments for ${\phi}$ , we note that

$\displaystyle \mathop{\mathbb P}_{(x_1,\ldots,x_n) \leftarrow S} [ x_1 = b] = \frac {\#\phi_{x \leftarrow b}} {\#\phi }$

Suppose then that we have an efficient sampling algorithm that given ${\phi}$ and ${\epsilon}$ generates a distribution ${\epsilon}$ -close to uniform over the satisfying assignments of ${\phi}$ .

Let us then ran the sampling algorithm with approximation parameter ${\epsilon/2n}$ and use it to sample about ${\tilde O(n^2/\epsilon^2)}$ assignments. By computing the fraction of such assignments having ${x_1=0}$ and ${x_1=1}$ , we get approximate values ${p_0,p_1}$ , such that ${| p_b - \mathop{\mathbb P}_{(x_1,\ldots,x_n) \leftarrow S} [ x_1 = b] | \leq \epsilon/n}$ . Let ${b}$ be such that ${p_b\geq 1/2}$ , then ${\#\phi_{x \leftarrow b}/p_b}$ is a good approximation, to within a multiplicative factor ${(1+2\epsilon/n)}$ to ${\#\phi}$ , and we can recurse to compute ${\#\phi_{x \leftarrow b}}$ to within a ${(1+2\epsilon/n)^{n-1}}$ factor.

Conversely, suppose we have an approximate counting procedure. Then we can approximately compute ${p_b = \frac {\#\phi_{x \leftarrow b}} {\#\phi }}$ , generate a value ${b}$ for ${x_1}$ with probability approximately ${p_b}$ , and then recurse to generate a random assignment for ${\#\phi_{x \leftarrow b}}$ .

The same equivalence holds, clearly, for 2SAT and, among other problems, for the problem of counting the number of perfect matchings in a bipartite graph. It is known that it is NP-hard to perform approximate counting for 2SAT and this result, with the above reduction, implies that approximate sampling is also hard for 2SAT. The problem of approximately sampling a perfect matching has a probabilistic polynomial solution, and the reduction implies that approximately counting the number of perfect matchings in a graph can also be done in probabilistic polynomial time.

The reduction and the results from last section also imply that 3SAT (and any other ${{\bf NP}}$ relation) has an approximate sampling algorithm that runs in probabilistic polynomial time with an ${{\bf NP}}$ oracle. With a careful use of the techniques from last week it is indeed possible to get an exact sampling algorithm for 3SAT (and any other ${{\bf NP}}$ relation) running in probabilistic polynomial time with an ${{\bf NP}}$ oracle. This is essentially best possible, because the approximate sampling requires randomness by its very definition, and generating satisfying assignments for a 3SAT formula requires at least an ${{\bf NP}}$ oracle.

One thought on “CS254 Lecture 8 – Approximate Counting”

anye on December 1, 2011 at 9:54 pm said:

Oh is there no further lecture notes?

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS254 Lecture 8 – Approximate Counting

One thought on “CS254 Lecture 8 – Approximate Counting”

Leave a Reply Cancel reply

Share this:

Like this:

Related

One thought on “CS254 Lecture 8 – Approximate Counting”

Leave a Reply Cancel reply