Critical behavior in the computational cost of satisfiability testing

DOI10.1016/0004-3702(95)00056-9OpenAlexW2084033406WikidataQ127673837 ScholiaQ127673837MaRDI QIDQ2674189

Scott Kirkpatrick, Bart Selman

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

complexityphase transitionsatisfiabilityfinite-size scalingdynamical critical phenomena\(k\)-satisfiabilitycomputational cost scaling

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

Generic properties of a computational task predict human effort and performance, Generating hard satisfiability problems, Some pitfalls for experimenters with random SAT, Implicates and prime implicates in random 3-SAT, The TSP phase transition, Biased random k‐SAT, Algorithm portfolios, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The hardest constraint problems: A double phase transition
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• The birth of the giant component
• A Computing Procedure for Quantification Theory