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)

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

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)