Some pitfalls for experimenters with random SAT

DOI10.1016/0004-3702(95)00049-6MaRDI QIDQ2674180zbMATH OpenOpenAlexFDO

Authors David G. Mitchell, Hector J. Levesque

Publication date 22 September 2022

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(95)00049-6

zbMATH Keywords

experimental designphase transitionsrandom problemssatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Generating hard satisfiability problems
• scientific article; zbMATH DE number 2010170
• scientific article; zbMATH DE number 1113991
• An improved generator for 3-CNF formulas
• scientific article; zbMATH DE number 956856

Cites work

• A Computing Procedure for Quantification Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A machine program for theorem-proving
• Algorithms for testing the satisfiability of propositional formulae
• Computational experience with an interior point algorithm on the satisfiability problem
• Critical behavior in the computational cost of satisfiability testing
• Generating hard satisfiability problems
• scientific article; zbMATH DE number 30299 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Resolution vs. cutting plane solution of inference problems: Some computational experience
• Solving the satisfiability problem by using randomized approach

Cited in

(8)

• Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes
• How to fake an RSA signature by encoding modular root finding as a SAT problem
• Backtracking algorithms for disjunctions of temporal constraints
• On SAT instance classes and a method for reliable performance experiments with SAT solvers
• Generating hard satisfiability problems
• SatEx: A web-based framework for SAT experimentation
• DPLL: the core of modern satisfiability solvers
• scientific article; zbMATH DE number 2010170 (Why is no real title available?)

This page was built for publication: Some pitfalls for experimenters with random SAT

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