Probabilistic approach to the satisfiability problem
type: Item
instance of: scholarly article
title: Probabilistic approach to the satisfiability problem
zbMATH Open document ID: 0732.68051
DOI: 10.1016/0304-3975(91)90316-T
author: Olivier Dubois
author: Jacques Carlier
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4211503
zbMATH Keywords: NP problem
zbMATH Keywords: probabilistic algorithms
zbMATH Keywords: satisfiability problem
MaRDI profile type: Publication
cites work: Q4138187
cites work: Counting the number of solutions for instances of satisfiability
cites work: Q4198056
cites work: Q3723699
Recommended article: Probabilistic satisfiability
Recommended article: A probabilistic study on the satisfiability problem
Recommended article: Theory and Applications of Satisfiability Testing
Recommended article: Q3081621
Recommended article: Probabilistic Reasoning by SAT Solvers
Recommended article: Q4014855
Recommended article: Probabilistic satisfiability with imprecise probabilities
Recommended article: A Hybrid Method for Probabilistic Satisfiability
description: scientific article; zbMATH DE number 4211503