Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Good question. Not an answer, but it's interesting that for the 3-SAT decision problem the hardness threshold is at around m/n=4.26 (the same location as the satisfiability threshold), whereas for #3-SAT it's around 1.5 (see Handbook of Satisfiability or ). So even for $k \geq 3$ the counting complexity hardness threshold is away from the decision threshold. I would be interested in seeing whether any rigorous work has been done for general k. – Huck Bennett Mar 16 '12 at 23:38

Perhaps this paper can help you:

New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter by J. Zhou, M. Yin, C. Zhou (2010).

And this one that studies the structure of the set of solutions of a random 2-SAT instance: Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps by G. Istrate (2007)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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