Critical behavior in the computational cost of satisfiability testing

DOI10.1016/0004-3702(95)00056-9MaRDI QIDQ2674189zbMATH OpenOpenAlexWikidataFDO

Authors Bart Selman, Scott Kirkpatrick

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)00056-9

zbMATH Keywords

\(k\)-satisfiabilitycomplexitycomputational cost scalingdynamical critical phenomenafinite-size scalingphase transitionsatisfiability

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

• scientific article; zbMATH DE number 1369843
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 2083805
• scientific article; zbMATH DE number 2080304
• Hard random 3-SAT problems and the Davis-Putnam procedure

Cites work

• A Computing Procedure for Quantification Theory
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1995157 (Why is no real title available?)
• The birth of the giant component
• The hardest constraint problems: A double phase transition

Cited in

(10)

• The TSP phase transition
• Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
• Solving non-uniform planted and filtered random SAT formulas greedily
• Generating hard satisfiability problems
• Some pitfalls for experimenters with random SAT
• Implicates and prime implicates in random 3-SAT
• Algorithm portfolios
• Biased random k‐SAT
• Phase transitions in quantum annealing of an NP-hard problem detected by fidelity susceptibility
• Generic properties of a computational task predict human effort and performance

This page was built for publication: Critical behavior in the computational cost of satisfiability testing

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