A model of random industrial SAT

DOI10.1016/j.tcs.2022.01.038MaRDI QIDQ2118866

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

SAT; random SAT; balls and bins problem; satisfiability threshold; industrial SAT

Mathematics Subject Classification ID

68Qxx: Theory of computing

Related Items

Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden

Uses Software

• Sat4j
• COMiniSatPS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating SAT instances with community structure
• A threshold for unsatisfiability
• The asymptotic \(k\)-SAT threshold
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Machine learning-based restart policy for CDCL SAT solvers
• On the satisfiability threshold of formulas with three literals per clause
• Tight lower bound on the probability of a binomial exceeding its expectation
• Poisson approximation for non-backtracking random walks
• The scaling window of the 2-SAT transition
• The Community Structure of SAT Formulas
• Proof of the Satisfiability Conjecture for Large k
• Impact of Community Structure on SAT Solver Performance
• Between SAT and UNSAT: The Fundamental Difference in CDCL SAT
• Approximating the unsatisfiability threshold of random formulas
• Balls and bins: A study in negative dependence
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method
• The probabilistic analysis of a greedy satisfiability algorithm
• The complexity of theorem-proving procedures