Regular random \(k\)-SAT: Properties of balanced formulas

DOI10.1007/s10817-005-9012-zzbMath1109.68100OpenAlexW1987851683MaRDI QIDQ862410

Yacine Boufkhad, Olivier Dubois, Bart Selman, Yannet Interian

Publication date: 24 January 2007

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-005-9012-z

zbMATH Keywords

greedy algorithm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Random k -SAT and the power of two choices ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Estimating satisfiability ⋮ Solving non-uniform planted and filtered random SAT formulas greedily

Cites Work

• A threshold for unsatisfiability
• Differential equations for random processes and random graphs
• Selecting Complementary Pairs of Literals
• Many hard examples for resolution
• The Forwarding Indices of Random Graphs
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Lower bounds for random 3-SAT via differential equations
• Upper bounds on the satisfiability threshold
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item