Self-reducible with easy decision version counting problems admit
additive error approximation. Connections to counting complexity,
exponential time complexity, and circuit lower bounds

arXiv:1611.01706v1 [cs.CC] 5 Nov 2016

Eleni Bakali
National Technical University of Athens, CS dept.
mpakali@corelab.ntua.gr
November 8, 2016
Abstract
We consider the class of counting problems,i.e. functions in #P, which are self reducible,
and have easy decision version, i.e. for every input it is easy to decide if the value of the
function f (x) is zero. For example, #independent-sets of all sizes, is such a problem, and one
of the hardest of this class, since it is equivalent to #SAT under multiplicative approximation
preserving reductions.
Using these two powerful properties, self reducibility and easy decision, we prove that all
problems/ functions f in this class can be approximated in probabilistic polynomial time within
′
an absolute exponential error ǫ · 2n , ∀ǫ > 0, which for many of those problems (when n′ =
n+constant) implies additive approximation to the fraction f (x)/2n . (Where n′ is the amount
of non-determinism of some associated NPTM).
Moreover we show that for all these problems we can have multiplicative error to the value
′
f (x), of any desired accuracy (i.e. a RAS), in time of order 22n /3 poly(n), which is strictly
smaller than exhaustive search. We also show that f (x) < g(x) can be decided deterministically
in time g(x)poly(n), ∀g.
Finally we show that the Circuit Acceptance Probability Problem, which is related to derandomization and circuit lower bounds, can be solved with high probability and in polynomial
time, for the family of all circuits for which the problems of counting either satisfying or unsatisfying assignments belong to TotP (which is the Karp-closure of self reducible problems with
easy decision version).

1

Introduction

In counting complexity we explore the computational complexity of functions that count the number
of solutions of a decision problem. In general, the counting versions of problems are computationally
more difficult than their decision versions. For example, given a DNF formula, it is easy to determine
if it is satisfiable, but it seems hard to count the number of its satisfying assignments. Another
example is counting independent sets of all sizes for a given graph. It is obvious that it is easy
to tell if there is some independent set of any size, since a single node always is an independent
set. However it is one of the hardest problems to count, or even approximate, the number of all
independent sets.
In this paper we consider the class of all self reducible problems with easy decision version. A
problem here is called self reducible if the computation on a given instance can be reduced to a
1

polynomial number of sub-instances of the same problem, and the the height of the corresponding
self-reducibility tree is polynomial in the size of the input. It is proven in [4] that the Karp closure of
self reducible with easy decision version is exactly the class TotP, which is the class of all functions
f for which there exist a non-deterministic polynomial time Turing Machine s.t. the number of
all computation paths on input x equals f (x) + 1. A great number of problems of interest in the
literature are self reducible, and many of them have easy decision version.
Examples of such problems, from many different scientific areas are #DNF-Sat, #Monotone-2Sat, #Non-Cliques, #NonIndependent Sets, NonNegative Permanent, Ranking, Graph reliability,
#matchings, computing the determinant of a matrix, computing the partition function of several
models from statistical physics, like the Ising and the hard-core model, counting colorings of a
graph with a number of colors bigger than the maximum degree, counting bases of a matroid,
#independent sets of all sizes [10], and many more. (Definitions of the above and references can
be found in [4, 6, 10]).
Since computing exactly counting problems seems hard (unless P=NP), a first question to ask
about them is their approximability status. Concerning multiplicative error, it is proven [8] that
for self reducible problems, even a polynomial multiplicative-error deterministic (or randomized)
algorithm can be transformed to an FPTAS (FPRAS respectively), which means that we can
approximate it to within any positive factor of approximation ǫ in time polynomial in n, 1/ǫ. So,
for a self-reducible problem either there exist an FPTAS (respectively FPRAS), either it is non
approximable to any polynomial factor unless P=NP (respectively P=RP).
The same holds even for problems with easy decision version. For example there is an FPRAS
for #DNF SAT (satisfying assignments of a DNF formula), but it is proved [7] that #SAT can
be reduced to #IS (independent sets of all sizes), under an approximation-preserving reduction, so
since #SAT is inapproximable unless NP=RP, the same holds for #IS.
So a second question to ask for such problems, especially if they are inapproximable within
a multiplicative error, is whether we can achieve an additive error, for the fraction of accepting
solutions over the space of solutions, (e.g. the number of independent sets over the number of all
subsets of nodes, or the number of satisfying assignments over 2n ). Even for problems that admit
multiplicative approximation, such an additive approximation algorithm is not comparable to a
multiplicative one, in the sense it can give either a better or a worse result, depending on the input.
It is better when the number of solutions is big, and worse if the number of solutions is very small.
We investigate this question and we give a randomized polynomial time algorithm with additive
error ǫ, ∀ǫ > 0, for all problems/functions in TotP.
Another question of interest is the exact (probably exponential) deterministic time of computing
or approximating such problems. We show, among other things, that we can have a randomized
approximation scheme (i.e. a multiplicative error as small as we want) in time O(ǫ−2 poly(n)22n/3 ),
which is strictly smaller than the exhaustive search solution.
Finally we have the following connection to derandomization and circuit lower bounds. There
is a well studied problem, the Circuit Acceptance Probability Problem (CAPP): given a circuit C
=
with n input gates, estimate the proportion of satisfying assignments, i.e. if p = #sat−assignments
2n
Prx [C(x) = 1], find p̂ = p ± ǫ, for e.g. ǫ = 1/6. This is connected to derandomization, and to circuit
lower bounds. In particular it is shown by Williams in [11], that if CAPP can be solved, even
non-deterministically, and even in time of order 2δn poly(n) for some δ < 1, then NEXP*P/poly.
We show that our algorithm can be used to solve the Circuit Acceptance Probability Problem
(CAPP) in polynomial time and with high probability, for the family of all circuits for which the
problems of either (a) counting the number of satisfying assignments, or (b) counting the number
of unsatisfying assignments, belong to TotP. For example, CNF formulas belong to this class, as
well as other kinds of circuits that we mention. We believe that this fact together with some
2

sharpening and combinations of the proofs in some references that we will mention (in the related
work section), will yield interesting, non trivial, circuit lower bounds. We have left the latter for
further research.

1.1

Our Contribution

Until now, problems in this class are treated individually, and algorithms are designed based on the
specific characteristics of each problem. We instead explore what can be done if we exploit their
two basic, common structural characteristics, which are self-reducibility and easy decision version.
Based on these properties, we present a randomized algorithm which achieves for every ǫ, an
′
additive ǫ approximation to the quantity p = f (x)/2n , with running time polynomial in the size
of the input and in 1/ǫ (precisely O(ǫ−2 )), where n′ is the amount of non-determinism for that
problem. This is the best we could expect in the sense that any multiplicative approximation
would imply NP=RP. We also show that for many interesting problems n′ = n + constant and so
all results hold with n′ substituted with n (i.e. the size of the input).
Our algorithms relies on non-uniform sampling, by a Markov chain that goes back and forth in
the internal nodes of the computation tree of the corresponding NPTM on the given input, (see
below for details on the basic ideas).
We also show that for any function f in this class we can decide deterministically if f (x) ≤ g(x)
in time g(x) · poly(n), where n is the size of input x.
We also show the following results, concerning exponential time approximability. Our algorithm
can be viewed as computing f (x) with an absolute error ǫ · 2n , ∀ǫ > 0, so by setting ǫ accordingly,
we get an absolute error of order 2(β+1)n/2 in time of order 2(1−β)n poly(n), ∀β ∈ (0, 1). We also
show that we can have in time of order (2(β+1)n/2 + 2(1−β)n )poly(n), ∀β ∈ (0, 1) and polynomial in
ǫ−2 time, approximation scheme, (i.e. we can get a multiplicative error ǫ, ∀ǫ > 0). All these running
times are better than the exhaustive search solutions.
Then we show how our algorithm can solve with high probability, in polynomial time, and for
every ǫ, the Circuit Acceptance Probability Problem, for all polynomial size circuits, for which the
problems of either (a) counting the number of satisfying assignments, or (b) counting the number
of unsatisfying assignments, belong to TotP, e.g. DNF formulas, CNF formulas, Monotone circuits,
Tree-monotone circuits, etc.
Concerning improvements and extensions, we have that for TotP this algorithm is the best we
can achieve unless NP=RP , and we have also that this kind of approximation is impossible to be
extended to #P unless NEXP*P/poly. If any of these conjectures holds, our results can be viewed
as a possible step towards proving that.

1.2

The basic ideas

A key element in our proof relies on a fact proved in [4] that the karp-closure of self-reducible
problems with easy decision version coincides with the counting class TotP. This is the class of
functions f in #P for which there exist a polynomial-time non-deterministic Turing Machine M,
such that for every input x, f (x) equals the total number of leaves of the computational tree of
M, minus 1. Moreover M can always be s.t. its computation tree is binary (although not full). So
f (x) also equals the number of internal nodes of this tree.
Our first idea is the following. Instead of trying to count the number of accepting paths/solutions
for the input, try to count the number of internal nodes of the computation tree of the corresponding
NPTM M. This approach doesn’t take into account any special characteristics of the problem at

3

hand, but only the structural properties we already mentioned. So it can be applied to any problem
in this class.
It is worth noting that in this way we reduce a problem whose set of solutions might be of some
unknown structure, difficult to determine and understand, to a problem whose ’set of solutions’
(the internal nodes of the tree) has the very particular structure of some binary tree of height
polynomial in n = |x|.
Our second idea is the following. In order to estimate the number of internal nodes of the
computation tree, we could try to perform uniform sampling, e.g. with a random walk. However a
random walk on a tree, in general needs time exponential in the height of the tree, (polynomial in
the number of nodes), and besides that, it can be proved that uniform sampling is impossible unless
NP=RP. So instead, we design a Markov Chain converging in polynomial time by construction,
but whose stationary distribution, although not uniform, gives us all the information needed to
estimate the number of nodes, and thus the value of the function.

1.3

Related work-Comparisons- Open Questions

We will give some related work, comparisons to our results, and open questions.
1.3.1

On Counting Complexity

Counting complexity started by Valiant in [1] where he defined #P and showed that computing
the Permanent is #P-complete under Cook reductions. For a survey on Counting Complexity see
chapter 17 in [6].
As shown by Zachos et.al. in [18], Cook reductions blur structural differences between counting
classes, so several classes inside #P have been defined and studied. #PE was defined in [3] by
Pagourtzis as the problems in #P with decision version in P, TotP was introduced in [2](see the
definition in the preliminaries section), and in [4] was shown that it coincides with the Karp-closure
of self reducible problems in #PE. Other classes related to TotP, with properties, relations, and
completeness results, were studied e.g. in [2, 3, 4, 20, 21, 22, 23, 30].
Concerning the approximability of problems in TotP, no unified approach existed until now.
Problems are studied individually, and for some of them it is shown that FPRAS exist(i.e. multiplicative approximation within any factor, in time polynomial in the size of the input and in
the inverse of the error), e.g. for counting satisfying assignments of DNF formulas [27], and for
counting perfect matchings [26], while for other it is proved that are inapproximable unless NP=P
(or NP=RP for the randomized case), e.g. #IS: counting independent sets of all sizes in a graph
[28, 29]. Collections on relevant results, proofs and references can be found (among other things)
in e.g. [24, 6, 10, 25, 9].
Two significant papers are related to our work. Firstly, Sinclair et.al. in [8] showed that for self
reducible problems, FPRAS is equivalent to uniform sampling, and that a polynomial factor approximation implies FPRAS. So problems in TotP either have an FPRAS, either are inapproximable
within a polynomial factor. Secondly, in [7] Goldberg et. al. defined approximation preserving
reductions, and classified problems according to their (multiplicative) approximability. They also
showed (among other things) that #IS, which is in TotP, is under approximation preserving reductions interreducible to #SAT, which is considered inapproximable, since its decision version is
NP-complete. Also in [19] is shown by Bordewich that there exist an infinite number of approximability levels between the polynomial factor and the approximability of #SAT, if NP6=RP.
So for TotP, polynomial-factor multiplicative error in polynomial time is impossible unless
NP=RP. Our results show that we can have (a) time strictly smaller than brute force for a RAS,

4

and (b) polynomial time for additive error.
We have to note here that the result about the RAS do not extend to #SAT through the
reduction of Goldberg in [7] that we mentioned earlier, because the reduction maps a formula on n
variables, to a graph on n2 vertices. However the additive error results extend to #SAT for CNF
formulas, through a reduction to DNF that preserves the number of variables.
As for the question whether we can have such an additive approximation for the whole #P, we
can’t rule out this possibility, but as we will see in the discussion on the connections with circuit
lower bounds, we know that this is impossible unless NEXP * P/poly.
Another interesting open question is to find inside TotP a structural characterization of the
class of problems that admit an FPRAS, i.e. to find what is the significant common property that
makes them approximable.
1.3.2

On Exponential Time Complexity

The study of the exponential time complexity of problems in NP has started by Impagliazzo et al in
[12] where they showed exponential hardness results. For #k-SAT there have been some algorithms
in the literature.
In [13] Stockmeyer proved that polynomial time randomized algorithms exist, with access to a
Σ2 P oracle. In [14] Taxler proved randomized, constant-factor approximation algorithms, of time
exponential but smaller than 2n · poly(m, n), where n is the number of variables and m the number
of clauses of the input, provided that k-SAT (decision version) is solvable in O(2cn md ) for some
0 < c < 1 and d ≥ 1 (i.e. provided that the ETH conjecture is false). In [15] Thurley gives
approximation scheme i.e. ∀ǫ > 0 can achieve multiplicative error ǫ in time O∗ (ǫ−2 cnk ) for ck < 2.
1
In [16] Impagliazzo et al gives randomized exact counting in time O∗ (2(1− 30k )n ). There is also an
algorithm, without theoretical guarantee, in [17] by Gomes et al. that implements Stockmeyer’s
idea with some SAT solver, with outstanding performance.
Since #3-SAT is #P-complete, all of TotP can be reduced to that, and so we can achieve such
approximations too, using the above algorithms.
However since counting is in general harder than decision, it is meaningful to explore the
exponential time complexity of counting even for problems with decision in P, since as we saw
already, they might be inapproximable in polynomial time.
Our algorithm for TotP is better than all the above, in the sense that we can have an approximation scheme in O(ǫ−2 2γn ) time, for all γ ∈ (2/3, 1), and without call to any oracle, and without
any unproven assumptions. Impagliazzo’s algorithm is better than ours in the sense that it gives
exact counting, and it is worse in running time. Note of course that through a reduction to 3-SAT,
if the number of variables of the resulting formula is more than n+constant, (where n would be
the size of the input of the original problem) the above algorithms perform even worse w.r.t. n.
We note again that deterministic/ randomized polynomial time approximation scheme for TotP
does not exist, unless P=NP/ NP=RP respectively . It is an open problem whether we can have
something in time superpolynomial and subexponential like nlog n .

1.4

On Circuit Lower Bounds

Excellent surveys on circuit complexity, as was the state of the art until 2009, can be found in
[39, 6]. Afterwards, progress has been made by Williams in [31], where he proved ACC circuit
lower bounds for NEXP and EN P , by finding improved algorithms for the circuit class ACC. His
work was based on ideas first presented in [11] where he proved connections between circuit lower
bounds and improved algorithms for Circuit-SAT.
5

There he also proved connections between solving the Circuit Acceptance Probability Problem
and circuit lower bounds. If CAPP can be solved for all circuits of polynomial size, even nondeterministically, and even in time of order 2δn poly(n) for some δ < 1, then NEXP*P/poly. He
also proved in [31, 38] that for any circuit family C closed under composition of circuits, improved
SAT algorithms imply E N P * C.
The CAPP problem was first defined and studied in relation to derandomization and circuit
lower bounds in [32, 33, 34, 35, 36]. In particular in [34] was shown that solving the CAPP in
subexponential nondeterministic time infinitely often, implies NEXP*P/poly.
We solve the CAPP in polynomial time, with high probability, for the family of all polynomial
size circuits, for which the problems of (a) counting the number of satisfying assignments, or (b)
counting the number of unsatisfying assignments, belong to TotP (e.g. for CNF formulas). We
believe that this result together with some combinations of the proofs in the above references, can
yield non-trivial lower bounds.

2

Preliminaries

We assume the reader is familiar with basic notions from computational complexity, like a nondeterministic Turing Machine, a boolean circuit, a CNF formula (formula in conjunctive normal
form), a DNF (disjunctive normal form) formula, and the classes NP, P, RP, NEXP, EXPN P ,
P/poly, #P, FP. For definitions see e.g. [6]. We also assume familiarity with some basics on
Markov chains, e.g. the notion of mixing time, and the stationary distribution. See e.g. [37].
We also keep the following conventions regarding the kinds of error for a value f . Absolute
error a: f ± a, additive error a: 2fn ± a, multiplicative error a: (1 ± a)f .
Definition 1 #P is the class of functions f : {0, 1}∗ → N for which there exists a non deterministic
polynomial time Turing machine (NPTM) Mf s.t. the number of accepting paths of Mf on input
x equals f (x).
#PE is the class of functions f in #P for which the decision version, i.e. the problem of
deciding if f (x) > 0, is in P.
TotP is the class of functions f : {0, 1}∗ → N for which there exists a non deterministic
polynomial time Turing machine (NPTM) Mf s.t. the number of all computation paths of Mf on
input x equals f (x) + 1.
Note that in the definition of TotP we take into account all paths, not only accepting paths like
in #P. Mf doesn’t need to return yes or no, but it can return anything, or just halt.
Important Observation It is proved in [20] that if for some function there exists an NPTM of
the kind described in the above definition for TotP, then for the same function there exists another
NPTM with the same properties, with the additional property that the non-deterministic choices
at each (non determinisitc) step are exactly 2. We will call such an NPTM ’binary’. Observe that
in this case, the computation tree has f (x) internal nodes, or ’branchings’, since it is binary. This
fact is extremely crucial for our proofs.
TotP is a subclass of #P. For a relation/problem A in NP we will call ’decision version’ the problem of deciding if there exist an accepting computation of some NPTM deciding problem A, and we
will call ’counting version’ the problem of counting accepting computations. For problems/functions
f in #P, or in TotP, we will call ’decision version, the problem of deciding if f (x) 6= 0.
It is proved in [4] that TotP is exactly the Karp-closure of self reducible problems in #PE,
under the following notion of self reducibility.
6

Definition 2 A function f : Σ∗ → N is called poly-time self-reducible if there exist polynomials r
and q, and polynomial time computable functions h : Σ∗ × N → Σ∗ , g : Σ∗ × N → N, and t : Σ∗ → N
such that for all x ∈ Σ∗ :
Pr(|x|)
(a) f (x) = t(x) + i=0 g(x, i)f (h(x, i)), that is, f can be processed recursively by reducing x to
h(x, i) (0 ≤ i ≤ r(|x|)),

(b) the recursion terminates after at most polynomial depth (that is, f h(...h(h(x, i1 ), i2 )..., iq(|x|) )
can be computed in polynomial time).

(c) |h(...h(h(x, i1 ), i2 )..., iq(|x|) | ∈ O poly(|x|) .

Intuitively a function f is self reducible if f (x) can be efficiently reduced to computing f (xi )
for some other instances xi , with the condition that if we continue the same procedure recursively,
the resulting recursion tree (whose nodes are the respective instances) will be of polynomial height.
Note that we will refer to this recursion tree as the ’self reducibility tree’.
For example circuit satisfiability problems are self reducible under this notion. The number of
solutions (i.e. satisfying assignments) of C equals the number of solutions of C1 , which is C with
its first input gate fixed to 1, plus the number of solutions of C0 , which is C with the first input
gate fixed to 0.
Of course circuit satisfiability is not in P (as far as NP6=P), so its counting version is not in
TotP.
To understand the definitions better, we will give another example of a problem in TotP, show
that it is self reducible, and give the corresponding NPTM (whose number of paths on input x
equals f (x) + 1).
The problem is #IS: given a graph G on n nodes, f (G) is the number of independent sets of all
sizes. Clearly f is in TotP, as a single node is always an independent set, and the self reducibility
tree can be defined as follows. f (G) equals the number of independent sets containing node 1 plus
the number of those not containing 1, so f (G) is reduced to f (G0 )+f (G1 ), where G0 is G with node
1 and its neighbourhood removed, and G1 is G with node 1 removed. We do that recursively for all
sub-instances that occur. So the height of the self reducibility tree is n. The corresponding NPTM
proceeds as follows. In each step i it checks whether for the corresponding sub-instances f (Gi0 ) and
f (Gi1 ) is not zero, and if both of them are, then it branches (i.e. it proceeds non deterministically),
else it proceeds deterministically to that sub-instance Gib for which f (Gib ) > 0, if such exists, else
it halts. Finally, in order to have in total f (G) + 1 leaves (or, equivalently, computation paths),
in the end of the whole computation, it makes one more branching in the rightmost path (the one
that has no ”left” choice in any level).
Note that in this case, the computation tree is exactly the same as the self reducibility tree,
with one more branching at the right end. And clearly the number of non deterministic bits used
by the NPTM is at most the height of the self reducibility tree plus one. This is because f (x)
results as a simple addition of f on two sub-instances. But this is not always the case, as the
definition of self reducibility is more general. On the other hand this is the case for many problems
defined on graphs and circuits, like counting satisfying assignments of monotone circuits, and of
DNF formulas.

3

Approximability of TotP

As we saw in the preliminaries section, the Karp closure of self reducible problems in #P E equals
the class TotP. Since the number of all paths of a (not necessarily full) binary tree, minus one,
equals the number of internal nodes of that tree, to compute a function in TotP, it suffices to
compute the number of branchings of the computation tree of the corresponding NPTM.
7

For a problem f in TotP, on input x, it is easy to check whether a state of some computation of the corresponding NPTM is a branching, as follows. We can associate each internal state
with the string of non-deterministic choices made to reach that state. Given such a string, we
simulate the NPTM M with these non-deterministic choices, until M either has to make another
non-deterministic choice, either it halts. In the first case we consider that state as a ’branching’,
in the second as a ’leaf’.
Thus, the problem of counting branches of such an NPTM in time polynomial in |x|, reduces to
the problem of counting nodes of a subtree S of the full binary tree T of height n, containing the
root of T (if S is not empty), in time polynomial in n, where S is given implicitly by some oracle
or poly-time predicate that tells us for every node of T if it belongs to S.
Lemma 1 For any f ∈TotP, on input x, computing f (x) in time poly(|x|) is reduced to counting
nodes of a subtree S of the full binary tree T of height n = poly(|x|), containing the root of T (if
S is not empty), in time polynomial in n, where S is given implicitly by some oracle or poly-time
predicate, that tells us for every node of T if it belongs to S.
We are going to give a probabilistic algorithm that given such a predicate for some subtree S,
approximates the size of S in time poly(n). It is based on a rapidly mixing Markov chain on the
nodes of S. We will first present the Markov chain and prove its mixing time and its stationary
distribution. Then we will show how we can approximate the size of S, using the Markov chain for
sampling from its stationary distribution.

3.1

The Markov Chain

We define a Markov chain, having as states the nodes of a subtree of the full binary tree.
Definition 3 Let S be a subtree of the fully binary tree T of height n, containing the root of T .
We define the Markov chain P over the nodes of S, with the following transition probabilities.
p(i, j) = 1/2 if j is the parent of i,
p(i, j) = 1/4 if j is a child of i,
p(i, j) = 0 forPevery other j 6= i, and
p(i, i) = 1 − j6=i p(i, j).

Proposition 1 The stationary distribution of the above Markov chain P is as follows. If di is the
n−di , where
depth of node i, i.e. its distance from
P the root, and n the height of the tree, ∀i, π(i) = α2
α is a normalizing factor, so that i π(i) = 1.

P
Proof. It is easy to check that i π(i)p(i, j) = π(j)

Now we will prove that P is rapidly mixing, i.e. polynomial in the height of the tree S. The
intuition is the following. The simple random walk on a tree needs time polynomial in the size
of the tree, which in the worst case of a fully binary tree, it is exponential in the height of the
tree. The reason is that it is difficult to go from a leaf to the root, since the probability of going
downwards the levels of the tree, is double the probability of going upwards. So we designed a walk
such that, on the full binary tree, the probabilities of going upwards equals the probability of going
downwards. So its easy to see that the mixing time equals the time of convergence to the uniform
distribution over the levels of the tree, thus polynomial to the height of the tree. (Of course what
we loose is that the new walk, as we saw, does not converge to the uniform distribution over the
nodes of S, as is the case for the simple random walk, and this is the reason we cannot get an
FPRAS with this approach.)
8

It turns out that this Markov chain converges quickly even in the general case. There are many
ways to prove the mixing time formally, and we present one of them. We will use the following
lemma from [8].
Let {Xt }t≥0 be a Markov chain over a finite state space X with transition probabilities pij ,
(t)
px be the distribution of Xt when starting from state x, π be the stationary distribution, τx (ǫ) =
(t)
min{t : ||px − π|| ≤ ǫ} be the mixing time when starting from state x. An ergodic Markov chain
is called time reversible if ∀i, j ∈ X , pij πi = pji πj . Let H be the underlying graph of the chain
for which we have an edge with weight wij = pij πi = pji πj for each i, j ∈ X . A Markov chain is
called lazy if ∀i ∈ X ,P
pii ≥ 12 . In [8] the conductance of a time reversible Markov chain is defined, as
P
/ wij
1
P ∈Y
follows Φ(H) = min i∈Y,j
i∈Y πi ≤ 2 .
πi , where the minimum is taken over all Y ⊆ X s.t. 0 <
i∈Y

Lemma 2 [8] For any lazy, time reversible Markov chain


1
−1
−1
(log πx + log ǫ ) .
τx (ǫ) ≤ const ×
Φ(H)2
Proposition 2 The mixing time of P , when starting from the root, is polynomial in the height of
the tree n.
Proof. First of all, we will consider the lazy version of the Markov chain, i.e. in every step, with
probability 1/2 we do nothing, and with probability 1/2 we follow the rules as in definition 3. The
mixing time of P is bounded by the mixing time of its lazy version. The stationary distribution
is the same. The Markov chain is time reversible, and the underlying graph is a tree with edge
weights wuv = πu puv = 2i α × 18 = 2i−3 α, if we suppose that u is the father of v and 2i α is the
probability πu .
Now it suffices to show that 1/Φ(H) is polynomial in n.
Let X be the set of the nodes of S, i.e. the state space of the Markov
P chain P . We will consider
/ wij
P ∈Y
.
all possible Y ⊆ X with 0 ≤ π(Y ) ≤ 1/2. We will bound the quantity i∈Y,j
i∈Y πi
If Y is connected and does not contain the root of S, then it is a subtree of S, with root let say
u, and πu = α2k for some k ∈ N. We have
X
wij ≥ wu,f ather(u) = 2k−2 α.
i∈Y,j ∈Y
/

Now let Y ′ be the full binary tree with root u and height the same as Y , i.e. k. We have
X
i∈Y

πi ≤

X

i∈Y ′

πi =

k
X

2k−j α × 2j = 2k (k + 1)α ≤ 2k (n + 1)α

j=0

where this comes if we sum over the levels of the tree Y ′ . So it holds
P
1
2k−2 α
w
P ij ≥ k
=
2 (n + 1)α
4(n + 1)
πi

If Y is the union of two subtrees of S, not containing the root of S, and the root of the first is
an ancestor of the second’s root, then the same arguments hold, where now take as u the root of
the first subtree.
If Y is the union of λ subtrees not containing the root of S, for which it holds that no one’s
root is an ancestor of any other’s root, then we can prove a same bound as follows. Let Y1 , ...Yλ be
9

the subtrees, and k1 , k2 , ..., kλ be the respective probabilities of the roots of them in the stationary
distribution. Then as before
X
wij ≥ 2k1 −2 α + 2k2 −2 α + ... + 2kλ −2 α
and
X

πi =

i∈Y

thus

X X

πi ≤ 2kj (n + 1)α

j=1...λ i∈Yj

P
P
α j=1...λ 2kj −2
wij
1
P
P
.
≥
=
4(n + 1)
πi
(n + 1)α j=1...λ 2kj

If Y is a subtree of S containing the root of S, then the complement of Y , i.e. S \ Y is the
union of λ subtrees of the previous form. So if we let Yi , ki be as before, then
X
X
wij = α
2kj −2
j=1...λ

and since from hypothesis π(Y ) ≤ 1/2, we have
X
X
X
πi ≤
πi ≤ (n + 1)α
2kj
i∈Y

j=1...λ

i∈S\Y

thus the same bound holds again.
Finally, similar arguments imply the same bound when Y is an arbitrary subset of S i.e. an
arbitrary union of subtrees of S.
In total we have 1/Φ(H) ≤ 4(n + 1).

Note that this result implies mixing time quadratic in the height of the tree, which agrees with
the intuition for the full binary tree, that it should be as much as the mixing time of a simple
random walk over the levels of the tree, i.e. over a chain of length n.
Before going on with the approximation algorithm, we will prove two properties of this Markov
chain, useful for the proofs that will follow.
Lemma 3 Let R be a binary tree of height n, and let αR be the normalizing factor of the stationary
1
n
distribution πR of the above Markov chain. It holds α−1
R ≤ (n + 1)2 , and πR (root) ≥ n+1
Proof. Let ri be the number of nodes in depth i.
1=

X

u∈S

πR (u) =

n
X

X

πR (u) =

i=0 u in level i

n
X
i=0

n

ri αR · 2n−i ⇒

X
1
ri · 2n−i
=
αR
i=0

which is maximized when the ri ’s are maximized, i.e. when the tree is full binary, in which case
n
n
ri = 2i and α−1
R = (n + 1)2 . This also implies that for the root of R it holds πR (root) = αR · 2 ≥
1

n+1 .

10

3.2

The approximation algorithm

Let S, T be as before. We will prove that we can approximate the number of nodes of S using the
previous Markov chain. The key idea is that much of the information we need is in the normalizing
factor α, and although the stationary distribution is far from being uniform over the nodes of S,
α is fully determined from the probability of the root, since we proved it to be 2n α, where n is the
height of S.
Let πS denote the probability distribution over the nodes of S, as defined in proposition 1, and
let αS denote the associated normalizing factor.
First we will show how we can compute exactly the number of nodes of S if we could somehow
(e.g. with an oracle, or an algorithm) know the normalizing factor αR for any subtree R of T
containing T ’s root.
Then we will give an approximation algorithm that relies on approximating all these factors
by sampling from the stationary distribution of the Markov chain described before, and estimating
the probability of the root, and from that, the corresponding αSi .
Finally we give the total error of our algorithm.
Proposition 3 Let S be a binary tree of height n, and ∀i = 0...n, let Si be the subtree of S that
contains all nodes up to depth i, and let αSi be the factors defined as above. Then
n−1

X 1
1
−
|S| =
αSn
αSk
k=0

Proof. For i = 1, ..., n let ri be the number of nodes in depth i. So |S| = r0 + ... + rn .
Obviously if S is not empty,
1
.
r0 = 1 =
αS0
We will prove that ∀k = 1...n

1
1
−2
,
αSk
αSk−1
Pn−1 1
) = αS1 − k=0
αS .

rk =
so then |S| =

1
αS0

+

Pn

1
k=1 ( αSk

− 2 αS1

k−1

n

(1)

(2)

k

We will prove claim (2) by induction.
For k = 1 we have
X
1
1
1
πS1 (u) = 1 ⇒ αS1 · r1 + 2αS1 · r0 = 1 ⇒ r1 =
− 2r0 =
−2
.
αS1
αS1
αS0
u∈S1

Suppose claim (2) holds for k < i ≤ n. We will prove it holds for k = i.
X

u∈Si

πSi (u) = 1 ⇒

i
X

i−1

2i−k αSi · rk = 1 ⇒ ri =

k=0

X
1
−
2i−k rk
αSi
k=0

and substituting rk for k = 0, ..., i − 1 by (1) and (2), we get ri =

1
αSi

− 2 αS1 .
i−1



Corollary 1 If we have an oracle, or a poly(n) predicate that for any subtree R gives the factor
αR defined as above, then we can compute exactly the number of nodes of any tree S of height n in
poly(n) time.

11

Now we can estimate αR for any tree R of height n, within (1 + ζ) for any ζ > 0, with high
probability, and in polynomial time, using the Markov chain over the nodes of R, given in Definition
3.
Proposition 4 For any binary tree R of height n we can estimate αR , within (1±ζ) for any ζ > 0,
with probability 1 − δ for any δ > 0, in time poly(n, ζ −1 , log δ−1 ).
Proof. Let R be a binary tree of height n. We can estimate αR as follows.
1
(which is the case when
As we saw, πR (root) = 2n αR , and we observe that this is always ≥ n+1
R is full binary). So we can estimate πR (root) within (1 ± ζ) for
any
ζ
>
0,
by sampling m nodes
P
1
X
,
where
Xi = 1 if the i-th
of R according to πR and taking, as estimate, the fraction p̂ = m
i=1 m i
sample node was the root, else Xi = 0.
It is known by standard variance analysis arguments that we need m = O(πR (root) · ζ −2 ) =
poly(n, ζ −1 ) to get
3
Pr[(1 − ζ)πR (root) ≤ p̂ ≤ (1 + ζ)πR (root)] ≥
4
We can boost up this probability to 1 − δ for any δ > 0, by repeating the above sampling
procedure t = O(log δ−1 ) times, and taking as final estimate the median of the t estimates computed
each time.
(Proofs for the above arguments are elementary in courses on probabilistic algorithms or statistics, see e.g. in [9] the unbiased estimator theorem and the median trick, for detailed proofs.)
The random sampling according to πR can be performed by running the Markov chain defined
earlier, on the nodes of R. Observe that the deviation ǫ from the stationary distribution can be
negligible and be absorbed into ζ, with only a polynomial increase in the running time of the
Markov chain.
Finally, the estimate for αR is αˆR = 2−n p̂, and it holds
Pr[(1 − ζ)αR ≤ αˆR ≤ (1 + ζ)αR ] ≥ 1 − δ.
The final algorithm for estimating |S| is as follows. We estimate αSi
we get an estimate of the size of S using proposition 3.


for every subtree of S and

Proposition 5 For all ξ > 0, δ > 0 we can get an estimate |Ŝ| of |S| in time poly(n, ξ −1 , log δ−1 )
s.t.
Pr[|S| − ξ2n ≤ |Ŝ| ≤ |S| + ξ2n ] ≥ 1 − δ
ξ
ζ
Proof. Let ζ = 2(n+1)
, thus poly(ǫ−1 ) = poly(ζ −1 ) = poly(n, ξ −1 ).
and ǫ = 1+ζ
So according to proposition 4 we have in time poly(n, ξ −1 , log δ−1 ) estimations ∀i = 1, ..., n

(1 − ǫ)αSi ≤ α̂Si ≤ (1 + ǫ)αSi .
(3)
P
n−1 1
We will use proposition 3. Let A = αS1 and B = k=0
αS , so |S| = A − B, and clearly B ≤ A.
n

k

1
1
A ≤ Â ≤ 1−ǫ
⇔ (1 − ζ)A ≤ Â ≤ (1 + ζ)A and similarly (1 − ζ)B ≤ B̂ ≤
From (3) we have 1+ǫ
(1 + ζ)B.
Thus (1 − ζ)A − (1 + ζ)B ≤ Â − B̂ ≤ (1 + ζ)A − (1 − ζ)B ⇔
A − B − ζ(A + B) ≤ Â − B̂ ≤ A − B + ζ(A + B), and since A ≥ B, we have
|S| − 2ζA ≤ |Ŝ| ≤ |S| + 2ζA. And since from lemma 3 the maximum A is 2n (n + 1), we have
|S| − 2ζ(n + 1)2n ≤ |Ŝ| ≤ |S| + 2ζ(n + 1)2n ⇔
|S| − ξ · 2n ≤ |Ŝ| ≤ |S| + ξ · 2n .


12

Corollary 2 Let p =
s.t.

|S|
2n .

For all ξ > 0, δ > 0 we can get an estimation p̂ in time poly(n, ξ −1 , log δ−1 )
Pr[p − ξ ≤ p̂ ≤ p + ξ] ≥ 1 − δ

So since, as we already discussed, every problem in TotP reduces to the above problem of
counting nodes of a tree, we proved the following theorem.
Theorem 1 For any problem f ∈ T otP , with Mf being its corresponding NPTM (whose total
number of computation paths on input x is f (x) + 1), and with n′ being the number of non deterministic bits used by Mf on input x, ∀ξ > 0, ∀x ∈ {0, 1}n we can have with heigh probability, in
′
time O(ǫ−2 , poly(n)) an estimation fˆ(x) = f (x) ± ξ · 2n .
′
Also corollary 2 holds for p = f (x)/2n , i.e. we can have p̂ = p ± ξ, ∀ξ > 0.
The above theorem holds with n in place of n′ , if n′ = n + constant, as is the case for many
problems like counting non-cliques of a graph, counting independent sets of all sizes of a graph,
counting non-independent sets of size k, counting satisfying assignments of DNF formulas, counting
satisfying assignments of monotone circuits, e.t.c.

4

Implications to exponential time complexity

In what follows, let f be a function in TotP, let M be the corresponding NPTM for which ∀x
(#branchings of M (x))= f (x). Let also n be the size of the input, or some complexity parameter
that we care about (e.g. the number of variables in a boolean formula or circuit), and n′ be the
amount of non-deterministic bits, that is the height of the computation tree of M (x) (where the
internal nodes are the branchings i.e. the positions where M makes a non-deterministic choice).
Of course n′ is polynomial in n. Be careful that n′ here is denoted n in proposition 5, as it is the
height of the tree. For the results to have some meaning, we consider functions s : N → N that are
positive, as small as we want, but at most O(2n ).
We give corollaries of the main result.
Corollary 3 For all f ∈ T otP , ∀s : N → N, ∀x ∈ {0, 1}∗ , ∀δ ∈ (0, 1), with probability 1−δ, in time
′
2n
−1 ), where n′ is as before, we can achieve an estimation fˆ(x) = f (x)±2n′ /2 s(n′ )1/2 .
′ poly(n, log δ
s(n )

′
′
For any β ∈ (0, 1), in time 2(1−β)n poly(n, log δ−1 ), we can achieve fˆ(x) = f (x) ± 2n (1+β)/2 .

Proof. From the proof of proposition 5 and in particular from the variance analysis arguments in
proposition 4, we can see that the actual dependence
q of′ the running time on ξ is proportional to
′
)
−2
ξ . So we get the first estimation by setting ξ = s(n
, and the second by setting s(n′ ) = 2βn .
2n′

For the consequent corollaries, we will need the following useful fact.
Theorem 2 For all f ∈ T otP , x, s as before, we can decide deterministically in time O(s(n) ·
poly(n)) whether f (x) ≤ s(n).
Proof. We perform a bfs or a dfs on the computation tree of M (x) (i.e. we perform exhaustive
search by trying all non deterministic choices) until we encounter at most s(n) + 1 branchings. If
the tree is exhausted before that time, then obviously f (x) ≤ s(n), else f (x) > s(n).

The next corollary shows that we can have a RAS (randomized approximation scheme) for every
problem in TotP, in time strictly smaller than that of exhaustive search. Note that we can’t have
that in polynomial time, unless NP=RP.
13

Corollary 4 For all f , x, s, δ, n, n′ as before, and for all k ∈ R, with probability 1 − δ and in
′
2n
n′ /2 s(n′ )1/2 ), we can achieve approximation fˆ(x) = f (x)(1 ± 1 ).
time poly(k, n, log δ−1 )( s(n
′) + 2
k
′

′

For every β ∈ (0, 1), we can have a RAS in time poly(k, n, log δ−1 )(2(1−β)n + 2(1+β)n /2 ).
We can also have uniform sampling in the same amount of time.
′

Proof. First we check deterministically if f (x) ≤ k2n /2 s(n′ )1/2 , in which case we get the exact
′
value of f (x). Otherwise, if f (x) > k2n /2 s(n′ )1/2 , we apply the initial algorithm to get fˆ =
′
f (x) ± 2n /2 s(n′ )1/2 which is < f (x) ± k1 f (x) = (1 ± k1 )f (x). The running time is a result from
theorem 2 and corollary 3.
We can also have uniform sampling, since in [8] is proved that a randomized approximation
scheme can be used for uniform sampling with a polynomial overhead in the running time.

Note that n′ in many cases, like problems on graphs, formulas, circuits etc., equals n+constant.
Some example is the problem #IS, as we discussed in the preliminaries section in detail.
Similar simple arguments hold for other problems too, so for these problems, since n′ = n +
constant, all the above corollaries hold with n′ substituted with n.
Corollary 5 For problems in TotP for which n′ = n + constant, like #IS, and #SAT for DNF
formulas, monotone circuits etc., all the above corollaries hold with n′ substituted with n.
We can explore whether we can extend corollary 4 for problems in #P. One possible way is to
find a (possibly of exponential time) approximation preserving reduction from a problem in #P to
a problem in TotP s.t. the amount of non-deterministic bits needed for the first doesn’t increase
too much with the reduction.
Precisely, if f is in #P with Mf being its corresponding NPTM (whose number of accepting
computation paths on input x is f(x)), that uses n non deterministic bits, and g is in TotP with Mg
its corresponding NPTM (whose total number of computation paths on input x equals f (x) + 1),
that uses n′ non deterministic bits, then we have the following.
Corollary 6 If there exists an approximation preserving reduction from a problem f ∈ #P to a
problem g ∈ T otP , s.t. n′ < (3 − γ)n/2), for some γ ∈ (0, 1), then for all x ∈ {0, 1}n , δ ∈ (0, 1),
k ∈ R, with probability 1−δ and in time t = poly(k, |x|, log δ−1 )(2(1−γ)n +2(1+γ)n/2 ), we can achieve
approximation fˆ(x) = f (x)(1 ± k1 ). The reduction suffices to be of time O(t), and not polynomial.
Proof. Apply corollary 4 on g with β ≥ 3 − nn′ (3 − γ).

Note that we took n, n′ to be the number of non deterministic bits, and not the sizes of the
inputs, because we want to compare with the running time of the brute force solutions.

5

Towards circuit lower bounds

There are two problems related to our results, that are related to derandomization and circuit lower
bounds too. The first one is the Circuit Acceptance Probability Problem (CAPP) where given a
boolean circuit with n input gates, and size nc for some c, and it is asked to approximate the
probability p = Prx [C(x) = 1] within some ǫ > 0, that is to find a p̂ = p ± ǫ. (In fact ǫ = 1/6
suffices for the results that follow). The second is the problem where given a circuit that has got
either 0 or > 2n−1 satisfying assignments, and it is asked if it is satisfiable. We will call it GapCSAT
(gap circuit satisfiability).
Their relationship with circuit lower bounds was proved in [34, 11]. The CAPP and its relation
to derandomization is studied in [32, 33, 34, 35, 36].
14

Theorem 3 [11] Suppose there is a superpolynomial s(n) s.t. for all c there is an O(2n ·poly(nc ))/s(n)
nondeterministic algorithm for CAPP on nvariables and nc gates. Then N EXP * P/poly. The
proof holds even if we replace CAPP with GapCSAT.
Since a randomized algorithm can be consider as a nondeterministic algorithm, our algorithm
yields a solution to CAPP for subclasses of polynomial size circuits, for wich the counting version is
in TotP, e.g monotone circuits, DNF formulas, and tree-monotone circuits. (The latter are circuits
monotone w.r.t. a partial order whose graph is a tree, and their counting version problem is the
basic TotP-complete problem under parsimonious reductions, as shown in [40]). The same holds for
circuits that can be reduced to circuits in TotP under additive-approximation preserving reductions,
like CNF formulas.
Corollary 7 CAPP can be solved with heigh probability (and thus non deterministically) in time
poly(n, ǫ−1 ), ∀ǫ > 0, for circuits with n input gates, whose counting version is in TotP, and the
height of the corresponding self-reducibility tree is n + constant.
Proof.
This is a result of corollary 2, where there n essentially denotes the height of the self
reducibility tree, as we already discussed in the previous subsection.

Corollary 8 CAPP can be solved with heigh probability in poly(n, ǫ−1 ), ∀ǫ > 0, for DNF formulas,
monotone circuits, tree-monotone circuits, and CNF formulas of poly(n) size and n input gates.
Proof. The problem of counting satisfying assignments of DNF formulas, monotone circuits, and
tree-monotone circuits, belongs to TotP.
To see that the corresponding self reducibility tree is of height n+constant, observe that the
number of sat.assignments of a DNF formula equals the sum of sat.assignments of the two DNF
subformulas that result when we set the first variable to 0 and 1 respectively.
The same holds for monotone circuits. For tree-monotone circuits the proof is more complicated,
see [40].
To see that the result holds for CNF formulas too, observe that if φ is a CNF formula, then
its negation φ̄ can easily be transformed to a DNF ψ with the same number of variables, using De
Morgan’s laws.
So if p = Prx [φ(x) = 1] and q = Prx [ψ(x) = 1], then p = 1− q. If q̂ = q ± ǫ then p̂ = 1− q̂ = p ± ǫ.

As for the GapCSAT problem, for circuits whose counting version problem is in TotP, is solved
in P by definition (of TotP). By our algorithm, it is also solved in randomized polynomial time, for
circuits for which the problem of counting non-satisfying assignments is in TotP, like CNFs, and in
particular it can be solved for any gap ρ, (i.e. the number of solutions is either 0 or > ρ2n .
Corollary 9 The GapCSAT problem, for any gap ρ, is in randomized polynomial time for circuits
s.t. (a)counting the number of solutions is in TotP, or (b)counting the number of non-solutions is
in TotP. (e.g. DNF, CNF).
Proof. If the number of solutions are either 0 or > ρ2n , then the number of non solutions are

either 2n or (1 − ρ)2n , so it suffices to apply our algorithm (theorem 1) with ξ = ρ/2.
These results, combined with proofs of the given references, could give some lower bounds for
circuits as the above. Also an additive approximation reduction even non deterministic, and even
in subexponential time, from circuit sat to a problem in TotP, would give lower bounds for P/poly.

15

Acknowledgements
I want to thank Manolis Zampetakis for mentioning to me the relationship between these results
and circuit lower bounds.

References
[1] L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science,
8(2), 189201, 1979.
[2] A. Kiayias, A. Pagourtzis, K. Sharma, and S. Zachos. The complexity of determining the order
of solutions. In Proceedings of the First Southern Symposium on Computing, Hattiesburg,
Mississippi, 1998.
[3] A. Pagourtzis. On the complexity of hard counting problems with easy decision version. In
Proceedings of the 3rd Panhellenic Logic Symposium, Anogia, Crete, 2001.
[4] A. Pagourtzis, S. Zachos. The complexity of counting functions with easy decision version. In
Proceedings of the 31st International Symposium on Mathematical Foundations of Computer
Science. Lecture Notes in Computer Science, vol. 4162, 741752, 2006.
[5] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[6] S. Arora, B. Barak. Computational Complexity: A Modern Approach. Cambridge University
Press New York, 2009.
[7] Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: The Relative
Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2003)
[8] Alistair Sinclair and Mark Jerrum. 1989. Approximate counting, uniform generation and
rapidly mixing Markov chains. Inf. Comput. 82, 1 (July 1989), 93-133.
[9] Alistair Sinclair,
Randomness and Computation,
lecture
https://people.eecs.berkeley.edu/ sinclair/cs271/n10.pdf

notes,

Fall

2011,

[10] Alistair Sinclair, Markov Chain Monte Carlo: Foundations and Applications, lecture notes,
Fall 2009 https://people.eecs.berkeley.edu/ sinclair/cs294/f09.html
[11] Ryan Williams, Improving exhaustive search implies superpolynomial lower bounds,Proceedings
of the 42nd ACM Symposium on Theory of Computing, STOC 2010,231–240
[12] Impagliazzo, R., Paturi, R., Zane, F. Which problems have strongly exponential complexity?
Journal of Computer and System Sciences 62(4), 512530 (2001) 6.
[13] L. Stockmeyer. On approximation algorithms for #P. SIAM J. Comput. 14 (1985) 849861.
[14] Patrick Traxler: The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments. Algorithmica 75(2): 339-362 (2016).
[15] M. Thurley, An approximation algorithm for #k-SAT, in: Proc. 29th Int. Symp. on Theoretical
Aspects of Computer Science (STACS), 2012, pp.78-87
[16] Impagliazzo, R., Matthews, W., Paturi, R.:A satisfiability algorithm for AC0. In: SODA 2012,
pp. 961972 (2012)
16

[17] C.P. Gomes, A. Sabharwal, and B. Selman. Model counting: A new strategy for obtaining good
bounds. In 21th AAAI, pages 5461, Boston, MA, July 2006.
[18] A. Kiayias, A. Pagourtzis, and S. Zachos. Cook reductions blur structural differences between
functional complexity classes. In: Panhellenic Logic Symposium, 132-137, 1999.
[19] M. Bordewich. On the Approximation Complexity Hierarchy. y. In Approximation and Online
Algorithms, pages 3746. Springer, 2011.
[20] A. Kiayias, A. Pagourtzis, K. Sharma, and S. Zachos. Acceptor-definable counting classes. In
Proceedings of the 8th Panhellenic conference on Informatics, 453-463, 2001.
[21] E. Bampas, A. Gbel, A. Pagourtzis, and A. Tentes. On the connection between interval size
functions and path counting. In Proc. of TAMC’09, LNCS 5532: 108117, Springer, 2009. Also
in Computational Complexity journal, doi: 10.1007/s00037-016-0137-8, pp. 1- 47, Springer,
June 2016.
[22] S.A. Fenner, L.J. Fortnow and S.A. Kurz: Gap definable counting classes, Proccedings 6th
Annual Structure in Complexity Theory Conference, pp.30-42, Chicago, IL, 1991. 453,454
[23] S.Saluja, K.V. Subrahmanyam and M.N. Thakur, Descriptive complexity of #P functions,
Journal of Computer and Systems Sciences 50 (1995), 493-505.
[24] O. Goldreich, Introduction to Complexity Theory, Lecture Notes Series of the Electronic
Colloquium on Computational Complexity, 1999, Chapter 10: ”#P and approximating it.”
http://www.eccc.uni-trier.de/eccc-local/ECCC-LectureNotes/
[25] V. Vazirani. Approximation algorithms. Springer, (2001)
[26] M. Jerrum and A. Sinclair. The Markov chain Monte-Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit
Hochbaum, ed.), PWS, pp. 482 520, 1996
[27] R.M. Karp, M. Luby, and N. Madras. Monte-Carlo approximation al- gorithms for enumeration
problems. Journal of Algorithms 10: 429448 (1989).
[28] M.Dyer, A. Frieze and M.Jerrum. On counting independent sets in sparse graphs. SIAM Journal
on Computing 31 (2002), pp. 1527-1541.
[29] D.Weitz. Counting independent sets up to the tree threshold. Proceedings of the 38th Annual
ACM Symposium on Theory of Computing (STOC), 2006, pp.140-149.
[30] L.A. Hemaspaandra, C.M. Homan, S. Kosub, and K.W. Wagner. The complexity of computing
the size of an interval. Technical Report cs.cc/0502058, ACM Computing Research Repository,
February 2005.
[31] R. Williams, Non-uniform ACC circuit lower bounds, IEEE Conference on Computational
Complexity, 2011, pp. 115125.
[32] B. Barak, A probabilistic-time hierarchy theorem for slightly non-uniform algorithms, in Proc.
RANDOM, Springer Lecture Notes in Comupt. Sci. 2483, 2002, pp. 194208.
[33] L. Fortnow, Comparing notions of full derandomization, in Proc. IEEE Conference on Computational Complexity, 2001, pp. 2834.
17

[34] R. Impagliazzo, V. Kabanets, and A. Wigderson, In search of an easy witness: Exponential
time versus probabilistic polynomial time, J. Comput. System Sci., 65 (2002), pp. 672694.
[35] V. Kabanets and J.-Y. Cai, Circuit minimization problem, in Proc. ACMSymposium on Theory
of Computing, 2000, pp. 7379.
[36] V. Kabanets, C. Rackoff, and S. A. Cook, Efficiently approximable real-valued functions,
Electronic Colloquium on Computational Complexity, TR00-034, 2000.
[37] D.Levin, Y. Peres, E. Wilmer: Markov chains and mixing times. AMS (2009).
[38] Ryan Williams: Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM
J. Comput. 42(3): 1218-1244 (2013)
[39] R. B. Boppana and M. Sipser. The complexity of finite functions. In J.van Leeuwen, editor,
Handbook of Theoretical Computer Science, volume 1.Elsevier and MIT Press, 1990.
[40] E. Bakali, A. Chalki, P. Pantavos, P. Pagourtzis, S. Zachos. TotP completeness under parsimonious reductions, manuscript.

18

