Probabilistic approach to the satisfiability problem (Q808705)

The authors investigate the satisfiability problem (SAT) from a probabilistic point of view. They propose a partition of the SAT into some classes of instances (according to the number of solutions in the classes) and show that the mean value of the numbers of solutions in these classes is independent from the distribution of variables. As a corollary the authors get a lower bound of the probability that a random instance, drawn from these classes, is contradictory. A connection between the dispersion of the number of solutions in classes and the number of occurrences of variables in the ``structure'' of an instance is investigated.