Some pitfalls for experimenters with random SAT

DOI10.1016/0004-3702(95)00049-6OpenAlexW2016239755MaRDI QIDQ2674180

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

phase transitionssatisfiabilityrandom problemsexperimental design

Mathematics Subject Classification ID

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

Related Items (5)

Generating hard satisfiability problems ⋮ How to fake an RSA signature by encoding modular root finding as a SAT problem ⋮ DPLL: The Core of Modern Satisfiability Solvers ⋮ Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes ⋮ Backtracking algorithms for disjunctions of temporal constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational experience with an interior point algorithm on the satisfiability problem
• 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
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Generating hard satisfiability problems
• Critical behavior in the computational cost of satisfiability testing
• Algorithms for testing the satisfiability of propositional formulae
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

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