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)

zbMATH Keywords

probabilistic algorithmssatisfiability problemNP problem

Mathematics Subject Classification ID

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

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

• 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?)
• Counting the number of solutions for instances of satisfiability

Cited in

(20)

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