Answers are grounded in this paper and cite their sources.
To compute the number of models of a 2-CF (conjunction of clauses with two literals at most), the well-known problem as #2-SAT, is a classical #P-complete problem. We show here an extensive class of instances of 2CF’s where to compute the number of models can be done in polynomial time. Given a 2-CF Σ, we show that if its constrained graph GΣ is acyclic or if its set of cycles can be arranged as a set of independent and embedded cycles then #2-SAT(Σ) can be computed in polynomial time. We present a procedure for detecting if a set of cycles can be embedded one into other. Furthermore, we design a polynomial reduction for given two restricted intersected cycles redraw those as embedded cycles. The resulting method for counting models for a 2-CF could be used to impact directly in the reduction of the complexity time of the algorithms for other counting problems. For example, for counting independent sets, counting colouring of graphs, counting cover vertex, etc.
No takes yet. Share an insight, caveat, or question.
Luna et al. (2007) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: