# Is #PP2DNF hard to approximate?

The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $$\phi$$ on variables $$X_1, \ldots, X_n, Y_1, \ldots, Y_m$$ of the form $$\bigvee_{1 \leq j \leq k} X_{n_j} \land Y_{m_j}$$. This problem is known to be #P-complete [Provan, J. S., Ball, M. O. (1983). The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4), 777-788.].

Is it known whether #PP2DNF is hard to approximate or not?

• What do you mean by approximate? There is an FPRAS for #DNF so it also works for #PP2DNF. – holf Feb 4 at 13:11
• @holf, I mean PTAS – Victor Feb 4 at 13:13