This post we will show that there is some hierarchy inside $\#\mathcal{P}$ when considering approximated solutions instead of exact solutions.

First note that if a clause contains a variable and its negation then immediately we can conclude that there are no satisfying assignments (s.a.) for that clause as it contains a contradiction, so we will omit it from the formula (can be done in linear time). So from now on, assume that $\psi$ do not contain any contradiction. For the rest of this discussion, we say that a boolean variable appear in a clause $C$ if either it or its negation contained in $C$ .

Let’s focus on an arbitrary clause $C_{i}\in\psi$ . We can easily count the number of s.a. it has; it is exactly $\#DNF\left(C_{i}\right)=2^{t}$ when $t\in\left\{ 0,1,..,n-1\right\}$ is the number of variables that do not appear in $C_{i}$ . That is true because the value of any variable in $C_{i}$ is determined by its appearance (if it has negation or not) so only variables which are not in $C_{i}$ can be either $True$ or $False$ and having two options.

Moreover, we can efficiently sample at uniform any s.a. for that clause. Simply iterate over the $n$ variables, if a variable appears in $C_{i}$ then it have only one allowed value so assign it that value, and if it is not appear in $C_{i}$ then toss a coin and assign $True$ or $False$ accordingly.

Trivial approximation algorithm will calculate the exact $\#DNF\left(C_{i}\right)$ for each $C_{i}$ in $\psi$ and returns their sum $k=\sum_{i=1}^{m}\#DNF\left(C_{i}\right)$ . However, we may have s.a. that were counted more than once (if they are satisfying more than a single clause). Thus the approximation factor of that algorithm is $m$ , because in the worst case all the clauses have the same set of satisfying assignments so we counted each s.a. $m$ times, yielding $k\le m\cdot k^{*}$ .

We can improve that algorithm by using the inclusion-exclusion principle: instead of accumulating the number of s.a. for each clause, accumulate the number of s.a. that weren’t count so far.

Unfortunately, finding which assignment was already counted forces us to enumerate all possible assignments, which obviously takes exponential time. Hence we will give a probabilistic estimation for that, instead. When working with estimations, we need to state the success probability for our estimation and it is also preferable that we will have a way to increase that probability (mostly at the cost of more computations and drawing more random samples).

Next section we will describe how to get an estimation of $k$ such that $\left(1-p\right)k^{*}\le k\le\left(1+p\right)k^{*}$ for any $p$ , even a polynomially small one (i.e. $p=\frac{1}{poly\left(n\right)}$ ) with a very high probability.

It left to show how to compute $\tilde{k}_{i}$ , so we do the following. Let $t=c\left(\frac{m}{p}\right)^{2}\ln m$ , when $c$ will be determined later. Sample $t$ independent times, an uniformly random s.a. for $C_{i}$ . For each assignment define a corresponding binary variable $X_{j}$ that is $1$ if it is not satisfying any previous clause, and $0$ otherwise. Note that evaluating all $\left\{ X_{j}\right\} _{j=1}^{t}$ takes $\mathcal{O}\left(poly\left(n,m\right)\cdot t\right)$ time. Then return $\tilde{k}_{i}=\frac{1}{t}\sum_{j=1}^{t}X_{j}$ . That completes our probabilistic approximation algorithm for $\#DNF$ .

Let $S_{i}$ be the number of all s.a. for $C_{i}$ and let $s_{i}$ be the number of s.a. for $C_{i}$ that aren’t satisfying any clause before $C_{i}$ . Out goal is to show that $\tilde{k}_{i}$ is, with high probability, close to $\frac{s_{i}}{S_{i}}$ . Observe that all the variables $\left\{ X_{j}\right\} _{j=1}^{t}$ for estimating $\tilde{k}_{i}$ were actually sampled i.i.d from a Bernoulli distribution with parameter $q_{i}=\frac{s_{i}}{S_{i}}$ (which is also its expectation). As a result $\mathbb{E}\left[\tilde{k}_{i}\right]=q_{i}$ , so apply Hoeffding inequality to get $$\begin{aligned} \mathbf{P}\left[\left|\tilde{k}_{i}-q_{i}\right|>\frac{p}{m}\right] & \le2\exp\left(\frac{-2\left(\frac{p}{m}\right)^{2}t^{2}}{t}\right)\\ & =2\exp\left(-2c\ln m\right)=2m^{-2c} \end{aligned}$$ which means that with high probability the estimator is “successful”, that is, $$q_{i}-\frac{p}{m}\le\tilde{k}_{i}\le q_{i}+\frac{p}{m}$$ and equivalently, $$s_{i}-S_{i}\frac{p}{m}\le\tilde{k}_{i}\cdot S_{i}\le s_{i}+S_{i}\frac{p}{m}$$ If all the estimators $\tilde{k}_{1},\tilde{k}_{2},..$ are successful, then $$k\le\sum_{i=1}^{m}\left(s_{i}+S_{i}\frac{p}{m}\right)=k^{*}+\sum_{i=1}^{m}S_{i}\frac{p}{m}\le k^{*}+\frac{p}{m}\left(mk^{*}\right)=\left(1+p\right)k^{*}$$ and also similarly $k\ge\left(1-p\right)k^{*}$ , which are exactly the approximation bounds that we want to achieve. To conclude the analysis, note that by applying the union bound, all the estimators will be successful with probability $\ge1-\sum_{i=1}^{m}2m^{-2c}=1-\frac{2}{m^{2c-1}}$ .

Consider the parameter $t$ , which is the number of samples the algorithm has to draw to estimate each $\tilde{k}_{i}$ . That $t$ depends linearly on the parameter $c$ which controls the “success probability” of all the estimators (simultaneously). On the one hand, large $c$ gives a success probability that is extremely close to $1$ . But on the other hand, it increase the number of samples $t$ per clause, and the total running time of the algorithm, which is $\mathcal{O}\left(poly\left(n,m\right)\cdot c\cdot p^{-2}\right)$ .

Similarly, the better approximation we want for $k^{*}$ , the smaller $p$ that we should set (even smaller than $1$ ), then the number of samples and the running time increase inversely proportional to $p^{2}$ .

Similarly, we can define an “easy” problem for $CNF$ formulas: decide whether a $CNF$ formula $\phi$ is a tautology can be done in polynomial time, by checking if its negation $\psi:=\neg\phi$ has a s.a. which is polynomial since $DNFSAT\in\mathcal{P}$ and $\psi$ is a $DNF$ formula.

As a conclusion, the hardness of those decision problems depends not only on the form of the formula but also on what are we asking to decide.