28
$\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?

$\endgroup$
  • $\begingroup$ See also related question cstheory.stackexchange.com/q/14953 $\endgroup$ – András Salamon Jan 12 '13 at 9:52
  • $\begingroup$ Do you mind explaining how you get the counting formula? Where does the 3! come from, etc? $\endgroup$ – Yan King Yin May 19 '15 at 1:17
  • $\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 May 19 '15 at 1:20
27
$\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

$\endgroup$
  • $\begingroup$ That is very interesting. What is the "overwhelming probability?" Is this something like 75%, or 99.9999%? $\endgroup$ – Philip White Oct 14 '10 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 Oct 14 '10 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 Oct 15 '10 at 9:47
17
$\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...

$\endgroup$
  • $\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 Apr 2 '17 at 16:50
4
$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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