Formally, $\mathcal{P}$ is the family of decision problems that can be solved in polynomial time. A known example is the Perfect Matching problem: given a graph, determine whether it has a perfect matching or not. A perfect matching is a set of edges that touches all the vertices in the graph and any pair of edges have disjoint endpoints.

The family $\mathcal{NP}$ contains all the decision problems that has polynomial time algorithm over the non-deterministic computational model (we won’t get into that). We know that $\mathcal{P}\subseteq\mathcal{NP}$ , but we don’t know if the other direction also holds. A famous $\mathcal{NP}$ -complete example is the Hamiltonian Cycle problem: given a graph, determine whether it contains a cycle that visits every vertex exactly once. We say “complete” to note that the problem is harder at least as any other problem inside that family, that is, if we could solve it efficiently (i.e. in polynomial time) then we could solve any other problem in the family efficiently. When a problem $P_{1}$ is at least harder as other problem $P_{2}$ we denote it $P_{1}\ge P_{2}$ .

Any problem in either $\mathcal{P}$ or $\mathcal{NP}$ can be rephrased slightly different. We can ask “how many perfect matching this graph contains?” rather than “is there a perfect matching in this graph?”. When asking how much instead of is there the problem become a Counting problem. Following that, the formal definition of $\#\mathcal{P}$ is: the family the Counting version of any problem in $\mathcal{NP}$ .

Notice that for any problem $P\in\mathcal{P}\cup\mathcal{NP}$ we have $P\le\#P$ because having a count of the desired property can, in particular, distinguish between the cases that this count is $0$ or higher, that is, decide whether that property exists or not. Hence, we can safely state the general hierarchy, that $\mathcal{P}\le\mathcal{NP}\le\#\mathcal{P}$ .

Let $P_{1},P_{2}$ be the Perfect Matching and Hamiltonian Cycle problems respectively, and let $\#P_{1},\#P_{2}$ be their Counting versions. It is interesting to see whether the hierarchy between problems from $\mathcal{P}$ and $\mathcal{NP}$ preserved for their Counting versions as well. For instance, for the problems above, we know that $P_{1}\le P_{2}$ since $\mathcal{P}\subseteq\mathcal{NP}$ and $P_{2}$ is $\mathcal{NP}$ -complete, is that implies also $\#P_{1}\le\#P_{2}$ ?

The short answer is no. In the next section we will show that in a detailed discussion.

We will need the following facts in the coming discussion:

It is very easy to solve DNF-SAT efficiently, meaning, in polynomial time. Given a $DNF$ formula $\psi$ , iterate over its clauses until you find a satisfiable clause then declare that $\psi$ is satisfiable, however, if you failed to find such a clause then declare that $\psi$ is not satisfiable. Observe that any clause of the form $C_{i}=\bigwedge_{j=1}^{\left|C_{i}\right|}\ell_{i,j}$ is satisfiable if and only if it does not contains a variable and its negation; which we can check with a single pass over the literals of $C_{i}$ . As a result, $DNFSAT\in\mathcal{P}$ .

In contrast to DNF-SAT, the CNF-SAT is know to be $\mathcal{NP}$ -complete, so we believe that it cannot be solved in polynomial time. Similar to the claim from the previous section, we conclude that CNF-SAT is “at least harder” as DNF-SAT, that is, $DNFSAT\le CNFSAT$ . However, as regard to the Counting versions of those problems, we can show the opposite inequality; that $\#CNFSAT\le\#DNFSAT$ .

To prove that, we need to show that if we could solve $\#DNFSAT$ efficiently, then we could solve $\#CNFSAT$ efficiently. So suppose we have a magical algorithm that can solve $\#DNFSAT$ in polynomial time. Given a $CNF$ formula $\phi$ over $n$ boolean variables, construct $\psi=\neg\phi$ and feed it to the magical algorithm. Let its output be the number $t$ , then return $2^{n}-t$ .

The correctness of that reduction follows from the two facts we stated earlier. Note that also all the procedures can be executed in polynomial time, so we solved $\#CNFSAT$ in polynomial time using an efficient solver for $\#DNFSAT$ , therefore, $\#CNFSAT\le\#DNFSAT$ .

Actually, if we will look closely on that reduction, we will see that it should work perfectly for the other direction as well, that is, solving $\#DNFSAT$ by a an efficient algorithm for the $\#CNFSAT$ , so we may conclude that both problems are equally hard. This is an evidence that the hierarchy between decision problems do not preserved for their Counting versions. Putting it differently, we can say that Counting makes problems much harder, such that even an “easy” problems from $\mathcal{P}$ become harder as the entire $\mathcal{NP}$ when you consider its Counting version.

An important property of the Cook-Levin reduction is that it keeps the number of s.a. for $\phi$ exactly as the number of witnesses for the original input $x$ of $P$ . That means, that we can use the same reduction to convert any Counting problem $\#P\in\#\mathcal{P}$ to $\#CNF$ . That is, the reduction will yields a procedure to convert any input $x$ for $\#P$ to a formula $\phi$ for $\#CNF$ such that the number of s.a. of $\phi$ is the solution for $\#P\left(x\right)$ . As a result, $\#CNF$ is $\#\mathcal{P}$ -complete, and then also $\#DNF$ .

Following the conclusion from previous section, we can say further that even a simple problem from $\mathcal{P}$ , can have a Counting version that is not just “harder” but harder as any other problem in $\#\mathcal{P}$ .

Next post we will discuss an approximation algorithm for $\#DNF$ and the hardness of approximating $\#CNF$ , showing that the additive relation from above it not enough for constructing an approximation algorithm for $\#CNF$ based on approximation for $\#DNF$ .