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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.