Consider a Monotone 3CNF formula having both the following additional restrictions:Every variable appears in exactly $2$ clauses.Given any $2$ clauses, they share at most $1$ variable.I would like to know how hard is counting the satisfying assignments of such a formula.Update 06/04/2013 12:55I would also like to know how hard is determining the parity of the number of satisfying assignments.Update 11/04/2013 22:40What if, in addition to the restrictions described above, we also introduce both the following restrictions:The formula is planar.The formula is bipartite.Update 16/04/2013 23:00Each satisfying assignment corresponds to an edge cover of a $3$-regular graph. After extensive search, the only relevant paper I was able to find on counting edge covers is the (3rd) one already mentioned in Yuval's answer. At the beginning of such paper, the authors say We initiate the study of sampling (and the related question of counting) of all edge covers of a graph. I'm very surprised that this problem has received so few attention (compared to counting vertex covers, which is widely studied and much better understood, for several graph classes). We do not know whether counting edge covers is $\#P$-hard. We do not know whether determining the parity of the number of edge covers is $\oplus P$-hard, either.Update 09/06/2013 07:38Determining the parity of the number of edge covers is $\oplus P$-hard, check answer below.
Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)
cc.complexity theory;sat;counting complexity