A model of random industrial SAT

DOI10.1016/J.TCS.2022.01.038MaRDI QIDQ2118866OpenAlexFDO

Authors D. Barak-Pelleg, Daniel Berend, J. C. Saunders

Publication date 23 March 2022

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

Full work available at URL https://arxiv.org/abs/1908.00089

zbMATH Keywords

SATrandom SATballs and bins problemsatisfiability thresholdindustrial SAT

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Generating SAT instances with community structure
• The community structure of SAT formulas
• Community structure in industrial SAT instances
• Popularity-similarity random SAT formulas
• On the hardness of SAT with community structure

Cites work

• scientific article; zbMATH DE number 3586221 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1249686 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 3008249 (Why is no real title available?)
• scientific article; zbMATH DE number 843222 (Why is no real title available?)
• scientific article; zbMATH DE number 3895112 (Why is no real title available?)
• A threshold for unsatisfiability
• Approximating the unsatisfiability threshold of random formulas
• Balls and bins: A study in negative dependence
• Between SAT and UNSAT: the fundamental difference in CDCL SAT
• Generating SAT instances with community structure
• Impact of Community Structure on SAT Solver Performance
• Machine learning-based restart policy for CDCL SAT solvers
• On the satisfiability threshold of formulas with three literals per clause
• Poisson approximation for non-backtracking random walks
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Proof of the satisfiability conjecture for large \(k\)
• The asymptotic \(k\)-SAT threshold
• The community structure of SAT formulas
• The complexity of theorem-proving procedures
• The probabilistic analysis of a greedy satisfiability algorithm
• The scaling window of the 2-SAT transition
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method
• Tight lower bound on the probability of a binomial exceeding its expectation

Cited in

(2)

• A Model of Random Industrial SAT
• Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden

Describes a project that uses

Uses Software

• Sat4j
• COMiniSatPS

This page was built for publication: A model of random industrial SAT

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