Probabilistic approach to the satisfiability problem

DOI10.1016/0304-3975(91)90316-TMaRDI QIDQ808705zbMATH OpenFDO

Authors Olivier Dubois, Jacques Carlier

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90316-T

zbMATH Keywords

NP problemprobabilistic algorithmssatisfiability problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Probabilistic satisfiability
• Probabilistic satisfiability
• A probabilistic study on the satisfiability problem
• Theory and Applications of Satisfiability Testing
• Probabilistic analysis of satisfiability algorithms
• Probabilistic Reasoning by SAT Solvers
• scientific article; zbMATH DE number 69384
• Probabilistic satisfiability with imprecise probabilities
• A hybrid method for probabilistic satisfiability

Cites work

• Counting the number of solutions for instances of satisfiability
• scientific article; zbMATH DE number 3954272 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(20)

• Probabilistic satisfiability
• Probabilistic performance of a heurisic for the satisfiability problem
• Probabilistic estimates for the generalized maximum satisfiability problem
• A kind of logical compilation for knowledge bases
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• A natural explanation for the minimum entropy production principle
• Probabilistic characterization of random Max r-Sat
• Probabilistic solution of Yao's millionaires' problem
• Counting the number of solutions for instances of satisfiability
• Refinement-oriented probability for CSP
• A probabilistic study on the satisfiability problem
• Satisfiability by Maxwell-Boltzmann and Bose-Einstein statistical distributions
• Partitioning search spaces of a randomized search
• scientific article; zbMATH DE number 3954272 (Why is no real title available?)
• scientific article; zbMATH DE number 69339 (Why is no real title available?)
• scientific article; zbMATH DE number 69384 (Why is no real title available?)
• scientific article; zbMATH DE number 1335882 (Why is no real title available?)
• scientific article; zbMATH DE number 1784977 (Why is no real title available?)
• On the complexity of probabilistic trials for hidden satisfiability problems
• scientific article; zbMATH DE number 4003523 (Why is no real title available?)

This page was built for publication: Probabilistic approach to the satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808705)