The probabilistic analysis of a greedy satisfiability algorithm

DOI10.1002/rsa.20104zbMath1099.68100OpenAlexW2602510746MaRDI QIDQ5486323

Lefteris M. Kirousis, Efthimios G. Lalas, Alexis C. Kaporis

Publication date: 6 September 2006

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20104

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT, An improved generator for 3-CNF formulas, An algorithm for random signed 3-SAT with intervals, An upper (lower) bound for Max (Min) CSP, The cook-book approach to the differential equation method, Satisfiability threshold for power law random 2-SAT in configuration model, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, On the lower bounds of random Max 3 and 4-SAT, Branching Process Approach for 2-Sat Thresholds, On the satisfiability threshold of formulas with three literals per clause, Unnamed Item, Unnamed Item, Super solutions of random \((3 + p)\)-SAT, When does the giant component bring unsatisfiability?, A model of random industrial SAT

Cites Work

• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Many hard examples for resolution
• Hard examples for resolution
• A sharp threshold in proof complexity
• A Computing Procedure for Quantification Theory
• Almost all graphs with average degree 4 are 3-colorable
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item