<p>On the one hand, the vast majority of the $2^{|C|}$ instances will be unsatisfiable, as said in Suresh's comment.  (In fact, I guess if you sample one such instance uniformly at random, you should already have a good probability of including all eight negations as clauses for some variable triple, i.e., trivially unsatisfiable.)</p>

<p>On the other, we may lower-bound the number of satisfiable instances by the number that are satisfied by the all-zero assignment: these would be $2^{(7/8)|C|}$, as for every triplet of variables there is one clause we may not use.</p>

<p>One may then upper-bound the number of satisfiable instances by multiplying this with $2^n$.  Since $|C|=O(n^3)$, I guess this only changes a minor-order term already...</p>

CC BY-SA 3.0
2017-04-02T16:50:34.793Z
When I first started my PhD studies, I showed that if the number of clauses for SAT were greater than $3^n-2^n$ then those instances were unsatisfiable. I also proved that if the number of clauses were in between the interval $3^n-2^n-2^{n-1}$ $<$ $number of clauses$ $\leq$ $3^n-2^n$ then those instances were either uniquely satisfiable or unsatisfiable. I do not recall the derivation for 3-SAT at the top of my head. Ok
Tayfun Pay
CC BY-SA 2.5
2010-10-18T12:20:15.603Z
2010-10-18T12:20:15.603Z
Magnus Wahlström
<p>This answer only deals with growth rate of the number of satisfiable instances.</p>

<p>A set $A$ is sparse if the number of n-bit strings in the set is bounded by $O(n^k)$ (for some constant $k$) otherwise it is dense. It is known that satisfiability (NP-complete) and Unsatisfiability (CoNP-complete) are both dense sets. There exists sparse $NP$-complete sets iff $P=NP$.</p>

CC BY-SA 2.5
2010-10-15T12:23:52.340Z
2010-10-15T12:23:52.340Z
Mohammad Al-Turkistany
<p>A long history of work on phase transitions in SAT has shown that for any fixed $n$, there's a threshold parametrized by the ratio of number of clauses to $n$ that decides satisfiability. Roughly speaking, if the ratio is less than 4.2, then with overwhelming probability the instance is satisfiable (and so a huge fraction of the number of instances with these many clauses and variables are satisfiable). If the ratio is slightly above 4.2, then the reverse holds - an overwhelming fraction of instances are unsatisfiable. </p>

<p>The references are way too many to cite here: one source of information is the book by <a href="http://tinyurl.com/2fg7zrk">Mezard and Montanari</a>. If anyone has sources for surveys etc on this topic, they could post it in comments or edit this answer (I'll make it CW)</p>

<p>References:
 <br>- <a href="http://users.soe.ucsc.edu/~optas/papers/handbook.pdf">Achlioptas survey</a>
 <br>- <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&amp;rep=rep1&amp;type=pdf">Where the really hard problems are</a>
 <br>- <a href="http://www.sciencedirect.com/science?_ob=MImg&amp;_imagekey=B6TYF-3VSNHP6-7-2&amp;_cdi=5617&amp;_user=10&amp;_pii=000437029500050X&amp;_origin=search&amp;_coverDate=03%2F31%2F1996&amp;_sk=999189998&amp;view=c&amp;wchp=dGLbVtz-zSkzS&amp;md5=ea1631da6d29e7e1712e56f66d274ff7&amp;ie=/sdarticle.pdf">Refining the phase transition in combinatorial search</a></p>

CC BY-SA 2.5
2010-10-14T18:41:02.047Z
I don't recall, to be honest. it's parametrized by the distance of the ratio from the switchover point, and acts like a sigmoid (so it goes to 1 very rapidly). The linked surveys probably have more detail
Suresh Venkat
CC BY-SA 2.5
2010-10-15T09:47:53.367Z
@Philip, Suresh: Yes it's a very rapid "discontinuity". If you see the plots, the probability to be satisfied changes abruptly from almost 1 to almost 0. It's interesting that the threshold depends on $k$. Also, it's interesting that all this behaviour seems to hold only for random instances.
Giorgio Camerani
CC BY-SA 2.5
2010-10-13T14:59:38.260Z
2010-10-25T12:38:27.437Z
2010-10-25T12:38:27.437Z
Suresh Venkat
<p>Consider the 3-SAT problem on n variables.  The number of possible distinct clauses is: </p>

<p>$$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$</p>

<p>The number of problem instances is the number of all subsets of the set of possible clauses: $I = 2^C$.  Trivially, for each $n \ge 3$, there exist at least one satisfiable instance and one unsatisfiable instance.
Is it possible to calculate, or at least estimate, the number of satisfiable instance for any given n?</p>

CC BY-SA 3.0
2013-01-12T09:52:49.873Z
See also related question http://cstheory.stackexchange.com/q/14953
András Salamon
CC BY-SA 3.0
2015-05-19T01:17:51.933Z
Do you mind explaining how you get the counting formula?  Where does the 3! come from, etc?
Yan King Yin
CC BY-SA 3.0
2015-05-19T01:20:18.240Z
Another newbie question: if the total number of configurations (ie, truth assignments) is $ 2^{2^n} \gg 2^C $, this means many truth assignments cannot be expressed by any problem instance.  That is counter-intuitive to my knowledge that boolean formulas are complete in the sense that they can express any truth table.  What's the catch here?
Yan King Yin
CC BY-SA 4.0
2020-10-02T17:09:36.130Z
@YanKingYin: Boolean formulas *are* complete, even if you restrict to CNF. However, if you restrict all clauses to have width at most 3, it is no longer complete in the usual sense (but it is in a generalized sense, if you allow adding additional "dummy" variables, as in the reduction from CNF-SAT to 3SAT).
Joshua Grochow
<cc.complexity-theory><sat>
How many instances of 3-SAT are satisfiable?
Antonio Valerio Miceli-Barone
# How many instances of 3-SAT are satisfiable?

(Asked by: username_0 on 2010-10-13)

Consider the 3-SAT problem on n variables. The number of possible distinct clauses is:

$$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$

The number of problem instances is the number of all subsets of the set of possible clauses: $I = 2^C$. Trivially, for each $n \ge 3$, there exist at least one satisfiable instance and one unsatisfiable instance.
Is it possible to calculate, or at least estimate, the number of satisfiable instance for any given n?

**Tags:** cc.complexity-theory, sat
> **Comments:**
> **username_1**: See also related question http://cstheory.stackexchange.com/q/14953  
> **username_2**: Do you mind explaining how you get the counting formula?  Where does the 3! come from, etc?  
> **username_2**: Another newbie question: if the total number of configurations (ie, truth assignments) is $ 2^{2^n} \gg 2^C $, this means many truth assignments cannot be expressed by any problem instance.  That is counter-intuitive to my knowledge that boolean formulas are complete in the sense that they can express any truth table.  What's the catch here?  
> **username_3**: @YanKingYin: Boolean formulas *are* complete, even if you restrict to CNF. However, if you restrict all clauses to have width at most 3, it is no longer complete in the usual sense (but it is in a generalized sense, if you allow adding additional "dummy" variables, as in the reduction from CNF-SAT to 3SAT).  

---

## 3 answers

### Answer by username_7 on 2010-10-13. Score: 29 | Accepted answer

A long history of work on phase transitions in SAT has shown that for any fixed $n$, there's a threshold parametrized by the ratio of number of clauses to $n$ that decides satisfiability. Roughly speaking, if the ratio is less than 4.2, then with overwhelming probability the instance is satisfiable (and so a huge fraction of the number of instances with these many clauses and variables are satisfiable). If the ratio is slightly above 4.2, then the reverse holds - an overwhelming fraction of instances are unsatisfiable.

The references are way too many to cite here: one source of information is the book by [Mezard and Montanari](http://tinyurl.com/2fg7zrk). If anyone has sources for surveys etc on this topic, they could post it in comments or edit this answer (I'll make it CW)

References:
  
- [Achlioptas survey](http://users.soe.ucsc.edu/~optas/papers/handbook.pdf)
  
- [Where the really hard problems are](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&rep=rep1&type=pdf)
  
- [Refining the phase transition in combinatorial search](http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYF-3VSNHP6-7-2&_cdi=5617&_user=10&_pii=000437029500050X&_origin=search&_coverDate=03%2F31%2F1996&_sk=999189998&view=c&wchp=dGLbVtz-zSkzS&md5=ea1631da6d29e7e1712e56f66d274ff7&ie=/sdarticle.pdf)

> **Comments:**
> **username_7**: I don't recall, to be honest. it's parametrized by the distance of the ratio from the switchover point, and acts like a sigmoid (so it goes to 1 very rapidly). The linked surveys probably have more detail  
> **username_8**: @Philip, Suresh: Yes it's a very rapid "discontinuity". If you see the plots, the probability to be satisfied changes abruptly from almost 1 to almost 0. It's interesting that the threshold depends on $k$. Also, it's interesting that all this behaviour seems to hold only for random instances.  

---

### Answer by username_4 on 2010-10-18. Score: 18

On the one hand, the vast majority of the $2^{|C|}$ instances will be unsatisfiable, as said in Suresh's comment. (In fact, I guess if you sample one such instance uniformly at random, you should already have a good probability of including all eight negations as clauses for some variable triple, i.e., trivially unsatisfiable.)

On the other, we may lower-bound the number of satisfiable instances by the number that are satisfied by the all-zero assignment: these would be $2^{(7/8)|C|}$, as for every triplet of variables there is one clause we may not use.

One may then upper-bound the number of satisfiable instances by multiplying this with $2^n$. Since $|C|=O(n^3)$, I guess this only changes a minor-order term already...

> **Comments:**
> **username_5**: When I first started my PhD studies, I showed that if the number of clauses for SAT were greater than $3^n-2^n$ then those instances were unsatisfiable. I also proved that if the number of clauses were in between the interval $3^n-2^n-2^{n-1}$ $<$ $number of clauses$ $\leq$ $3^n-2^n$ then those instances were either uniquely satisfiable or unsatisfiable. I do not recall the derivation for 3-SAT at the top of my head. Ok  

---

### Answer by username_6 on 2010-10-15. Score: 5

This answer only deals with growth rate of the number of satisfiable instances.

A set $A$ is sparse if the number of n-bit strings in the set is bounded by $O(n^k)$ (for some constant $k$) otherwise it is dense. It is known that satisfiability (NP-complete) and Unsatisfiability (CoNP-complete) are both dense sets. There exists sparse $NP$-complete sets iff $P=NP$.


---

