The satisfiability threshold for randomly generated binary constraint satisfaction problems

DOI10.1002/rsa.20118zbMath1094.68092OpenAlexW4301417336WikidataQ57401505 ScholiaQ57401505MaRDI QIDQ5471050

Alan M. Frieze, Michael S. O. Molloy

Publication date: 6 June 2006

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

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

zbMATH Keywords

resolution complexity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

Cites Work

• When does the giant component bring unsatisfiability?
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Models and thresholds for random constraint satisfaction problems
• A sharp threshold in proof complexity
• Random constraint satisfaction: A more accurate picture

This page was built for publication: The satisfiability threshold for randomly generated binary constraint satisfaction problems