Probabilistic approach to the satisfiability problem (Q808705)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Probabilistic approach to the satisfiability problem |
scientific article |
Statements
Probabilistic approach to the satisfiability problem (English)
0 references
1991
0 references
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.
0 references
NP problem
0 references
probabilistic algorithms
0 references
satisfiability problem
0 references