The permanent, graph gadgets and counting solutions for certain types of planar formulas

Christian Schridde

In this paper, we build on the idea of Valiant \cite{Val79a} and Ben-Dor/Halevi \cite{Ben93}, that is, to count the number of satisfying solutions of a boolean formula via computin…