Counting Problems
Today we describe counting problems and the class that they define, and we show that every counting problem
can be approximately solved in randomized polynomial given access to an
oracle.
1. Counting Classes
[Note: we did not cover most of the material of this section in class.]
Recall that is an NP-relation, if there is a polynomial time algorithm
such that
and there is a polynomial
such that
.
Definition 1 If
is an
relation, then
is the problem that, given
, asks how many
satisfy
.
is the class of all problems of the form
, where
is an NP-relation.
Observe that an NP-relation naturally defines an
language
, where
, and every
language can be defined in this way. Therefore problems in
can always be seen as the problem of counting the number of witnesses for a given instance of an
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
to
(written
) if there is a polynomial time transformation
such that for all
,
.
Often this definition is a little too restrictive and we use the following definition instead.
Definition 3
if there is a polynomial time algorithm for
given an oracle that solves
.
is the problem where given a circuit, we want to count the number of inputs that make the circuit output 1.
Theorem 4
is
-complete under parsimonious reductions.
Proof: Let be in
and
and
be as in the definition. Given
we want to construct a circuit
such that
. We then construct
that on input
simulates
. From earlier arguments we know that this can be done with a circuit with size about the square of the running time of
. Thus
will have size polynomial in the running time of
and so polynomial in
. Then let
.
Theorem 5
is
-complete.
Proof: We show that there is a parsimonious reduction from to
. That is, given a circuit
we construct a Boolean formula
such that the number of satisfying assignments for
is equal to the number of inputs for which
outputs 1. Suppose
has inputs
and gates
and
has inputs
, where the
represent the output of gate
. 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
to a formula
with
variables and
clauses. So there is a parsimonious reduction from
to
.
Notice that if a counting problem is
-complete under parsimonious reductions, then the associated language
is NP-complete, because
implies
. On the other hand, with the less restrictive definition of reducibility, even some counting problems whose decision version is in P are
-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
-complete.
2. Complexity of counting problems
We will prove the following theorem:
Theorem 6 For every counting problem
in
, there is a probabilistic algorithm
that on input
, computes with high probability a value
such that
in time polynomial in
and in
, using an oracle for
.
The theorem says that can be approximate in
. We remark that approximating
is
-hard, and so to compute an approximation we need at least the power of
. Theorem 6 states that the power of
and randomization is sufficient.
Another remark concerns the following result.
Theorem 7 (Toda) For every
,
.
This implies that is
-hard for every
, i.e.,
lies outside the polynomial hierarchy, unless the hierarchy collapses. Recall that
lies inside
, and hence approximating
can be done in
. Therefore, approximating
cannot be equivalent to computing
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
and that approximate counting is doable in
it does not necessarily follow that approximate counting is in
, although in this case it does because the proof that
relativizes; (ii) we have defined
,
, 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
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
.
If we have an approximation algorithm for
, we can extend it to any
in
using the parsimonious reduction from
to
.
- It is enough to give a polynomial time
-approximation for
.
Suppose we have an algorithm
and a constant
such that
Given
, we can construct
where each
is a copy of
constructed using fresh variables. If
has
satisfying assignments,
has
satisfying assignments. Then, giving
to the algorithm we get
If
is a constant and
,
.
- For a formula
that has
satisfying assignments,
can be found in
.
This can be done by iteratively asking the oracle the questions of the form: “Are there
assignments satisfying this formula?” Notice that these are
questions, because the algorithm can guess these
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
then
with high probability;
- If
then
with high probability.
Given a-comp, we can construct an algorithm that -approximates
as described below:
- Input:
- compute:
-
- if
outputs NO from the first time then
- // The value is either
or
and the answer can be checked by one more query to the
oracle.
- Query to the oracle and output an exact value.
- // The value is either
- else
- Suppose that it outputs YES for
and NO for
- Output
- Suppose that it outputs YES for
We need to show that this algorithm approximates within a factor of
. 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
and says NO for
. Since
outputs YES,
, and also since
outputs NO,
. The algorithm outputs
. Hence,
and the algorithm outputs the correct answer with in a factor of .
Thus, to establish the theorem, it is enough to give a 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 we pick a hash function
from a pairwise independent family, and look at the number of assignments
that satisfy
and such that
.
In the Valiant-Vazirani reduction, we proved that if is a set of size approximately equal to the size of the range of
, then, with constant probability, exactly one element of
is mapped by
into
. 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
is sufficiently larger than the range of
then the number of elements of
mapped into
is concentrated around its expectation.
Lemma 8 Let
be a family of pairwise independent hash functions
. Let
,
. Then,
From this, a-comp can be constructed as follows.
- input:
- if
then check exactly whether
.
- if
- pick
from a set of pairwise independent hash functions
, where
- answer YES iff there are more then
assignments
to
such that
satisfies
and
.
- pick
Notice that the test at the last step can be done with one access to an oracle to . We will show that the algorithm is in
. Let
be the set of satisfying assignments for
. There are 2 cases.
- If
, by Lemma 8 we have:
(set
, and
, because
)
which is the success probability of the algorithm.
- If
:
Let
be a superset of
of size
. We have
(by Lemma 8 with
.)
Therefore, the algorithm will give the correct answer with probability at least , which can then be amplified to, say,
(so that all
invocations of a-comp are likely to be correct) by repeating the procedure
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 , and pick a random
. We define random variables
as
Clearly, .
We now calculate the expectations. For each ,
and
. Hence,
Also we calculate the variance
Because are pairwise independent,
Using Chebyshev’s Inequality, we get
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 , given an input
, what is the size of the set
? A related question is to be able to sample from the uniform distribution over
.
Whenever the relation 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
and
to approximate within
the value
if and only if there is a probabilistic algorithm running in time polynomial in
and
that samples a distribution
-close to the uniform distribution over
.
We show how the above result applies to 3SAT (the general result uses the same proof idea). For a formula , a variable
and a bit
, let us define by
the formula obtained by substituting the value
in place of
.\footnote{ Specifically,
is obtained by removing each occurrence of
from the clauses where it occurs, and removing all the clauses that contain an occurrence of
; the formula
is similarly obtained.}
If is defined over variables
, it is easy to see that
Also, if is the uniform distribution over satisfying assignments for
, we note that
Suppose then that we have an efficient sampling algorithm that given and
generates a distribution
-close to uniform over the satisfying assignments of
.
Let us then ran the sampling algorithm with approximation parameter and use it to sample about
assignments. By computing the fraction of such assignments having
and
, we get approximate values
, such that
. Let
be such that
, then
is a good approximation, to within a multiplicative factor
to
, and we can recurse to compute
to within a
factor.
Conversely, suppose we have an approximate counting procedure. Then we can approximately compute , generate a value
for
with probability approximately
, and then recurse to generate a random assignment for
.
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 relation) has an approximate sampling algorithm that runs in probabilistic polynomial time with an
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
relation) running in probabilistic polynomial time with an
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
oracle.
Oh is there no further lecture notes?