<p>Perhaps this paper can help you:</p>

<p><a href="http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/download/1672/1961">New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter</a> by J. Zhou, M. Yin, C. Zhou (2010).</p>

<p>And this one that studies the structure of the set of solutions of a random 2-SAT instance: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8036&amp;rep=rep1&amp;type=pdf">Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps</a> by G. Istrate (2007)</p>

CC BY-SA 3.0
2012-03-16T23:30:51.273Z
2012-03-16T23:30:51.273Z
Marzio De Biasi
<p>Has any work been done on how the complexity of random instances of <strong>#2-SAT</strong> varies with the clause density? That is: how does <em>the difficulty of counting</em> satisfying solutions to a randomly generated instance of <strong>2-SAT</strong> vary, as the clause density varies? In particular, are there any rigorous results known involving critical thresholds?</p>

<p>Of course, because  <strong>2-SAT</strong>&nbsp;&isin;&nbsp;<strong>P</strong>, the typical counting complexity depends partly on the probability with which an instance is satisfiable; instances whose clause density is above the <a href="http://pre.aps.org/abstract/PRE/v56/i2/p1357_1">critical threshold for SAT/UNSAT</a> will typically have an easy counting complexity, as the answer is "<em>zero</em>" almost surely, in the limit <em>n</em>&nbsp;$\to \infty$. However, the counting complexity may still be easy for instances of <strong>2-SAT</strong> having a density near to or just above the critical threshold for finite <em>n</em>: 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. </p>

<p>For <strong><em>k</em>-SAT</strong> with <em>k</em>&nbsp;&ge;&nbsp;3, the <a href="http://www.cs.cornell.edu/selman/papers/pdf/96.aij.critical_behavior_cost.pdf">difficulty of determining whether an instance is satisfiable or unsatisfiable</a>  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 <em>at least one</em> satisfying solution. For <strong>#2-SAT</strong>, the difficulty <em>cannot</em> 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 <em>significant but not large</em> number of constraints &mdash; 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.</p>

CC BY-SA 3.0
2012-03-16T23:38:02.423Z
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
<cc.complexity-theory><counting-complexity><random-k-sat>
What is the counting complexity of random 2-SAT?
Niel de Beaudrap
# What is the counting complexity of random 2-SAT?

(Asked by: username_0 on 2012-03-16)

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](http://pre.aps.org/abstract/PRE/v56/i2/p1357_1) 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](http://www.cs.cornell.edu/selman/papers/pdf/96.aij.critical_behavior_cost.pdf) 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.

**Tags:** cc.complexity-theory, counting-complexity, random-k-sat

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-03-16. Score: 12

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](http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/download/1672/1961) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8036&rep=rep1&type=pdf) by G. Istrate (2007)


---

