Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated instance of 2-SAT vary, as the clause density varies? In particular, are there any rigorous results known involving critical thresholds?
Of course, because 2-SAT ∈ P, the typical counting complexity depends partly on the probability with which an instance is satisfiable; instances whose clause density is above the critical threshold for SAT/UNSAT will typically have an easy counting complexity, as the answer is "zero" almost surely, in the limit n $\to \infty$. However, the counting complexity may still be easy for instances of 2-SAT having a density near to or just above the critical threshold for finite n: one might expect that a satisfiable instance will have only a small number of solutions, which might be easy to enumerate due to the tightness of the constraints.
For k-SAT with k ≥ 3, the difficulty of determining whether an instance is satisfiable or unsatisfiable seems to be highest near the critical thresholds separating the SAT phase from the UNSAT phase, in part as one tries to determine whether there exists at least one satisfying solution. For #2-SAT, the difficulty cannot lie in determining whether at least one solution exists; so one should expect that the difficulty is likely to be in determining the number of solutions for satisfiable formulae of a significant but not large number of constraints — that is, where there are enough constraints to induce non-trivial dependencies between variables, but not so many as to over-determine the possible assignments.
