<p>The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula <span class="math-container">$\phi$</span> on variables <span class="math-container">$X_1, \ldots, X_n, Y_1, \ldots, Y_m$</span> of the form <span class="math-container">$\bigvee_{1 \leq j \leq k} X_{n_j} \land Y_{m_j}$</span>. This problem is known to be #P-complete [<em>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.</em>].</p>

<p>Is it known whether #PP2DNF is hard to approximate or not? </p>

CC BY-SA 4.0
2019-02-04T13:11:53.523Z
What do you mean by approximate? There is an FPRAS for #DNF so it also works for #PP2DNF.
holf
CC BY-SA 4.0
2019-02-04T13:13:25.220Z
@holf, I mean PTAS
Victor
<cc.complexity-theory><counting-complexity><approximation-hardness>
Is #PP2DNF hard to approximate?
Victor
# Is #PP2DNF hard to approximate?

(Asked by: username_0 on 2019-02-04)

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?

**Tags:** cc.complexity-theory, counting-complexity, approximation-hardness

> **Comments:**
> **username_1**: What do you mean by approximate? There is an FPRAS for #DNF so it also works for #PP2DNF.  
> **username_0**: @username_1, I mean PTAS  

---

## 0 answers

