Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of each formula?

The reference that have been working with is the Computational Complexity: A Modern Approach book, in which the idea of setting it as a CNF-SAT problem to sure it is #P complete, thus the number of satisfying assignments for f(x) is equal to the number of certificates for x. I understand that maybe am approaching it wrong but the most similar theorem found is the Valiant and can not seem to find arithmetic related counting complexity.

New contributor
Arnau M. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

1 Answer 1


$$ (x \land F) \lor (\lnot x \land G) $$


Your Answer

Arnau M. is a new contributor. Be nice, and check out our Code of Conduct.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.