31
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ See also related question cstheory.stackexchange.com/q/14953 $\endgroup$
    – András Salamon
    Commented Jan 12, 2013 at 9:52
  • 1
    $\begingroup$ Do you mind explaining how you get the counting formula? Where does the 3! come from, etc? $\endgroup$
    – Yan King Yin
    Commented May 19, 2015 at 1:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – Yan King Yin
    Commented May 19, 2015 at 1:20
  • 1
    $\begingroup$ @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). $\endgroup$
    – Joshua Grochow
    Commented Oct 2, 2020 at 17:09

3 Answers 3

Reset to default
29
$\begingroup$

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. 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
- Where the really hard problems are
- Refining the phase transition in combinatorial search

Improve this answer
$\endgroup$
3
  • $\begingroup$ That is very interesting. What is the "overwhelming probability?" Is this something like 75%, or 99.9999%? $\endgroup$
    – user1338
    Commented Oct 14, 2010 at 17:59
  • $\begingroup$ 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 $\endgroup$
    – Suresh Venkat
    Commented Oct 14, 2010 at 18:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – Giorgio Camerani
    Commented Oct 15, 2010 at 9:47
18
$\begingroup$

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...

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Tayfun Pay
    Commented Apr 2, 2017 at 16:50
5
$\begingroup$

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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