The SAT-UNSAT transition for random constraint satisfaction problems

DOI10.1016/j.disc.2008.04.025zbMath1185.68639OpenAlexW2047532073MaRDI QIDQ1025462

Hervé Daudé, Nadia Creignou

Publication date: 19 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.025

zbMATH Keywords

phase transitionsatisfiabilityconstraint satisfactionsharp thresholdsrandom structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Satisfiability Thresholds beyond k −XORSAT ⋮ An algorithm for random signed 3-SAT with intervals ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

Cites Work

• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Supersaturated graphs and hypergraphs
• Threshold functions
• Generalized satisfiability problems: Minimal elements and phase transitions.
• The phase transition in a random hypergraph
• Networks of constraints: Fundamental properties and applications to picture processing
• A sharp threshold for a random constraint satisfaction problem
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Sharp thresholds of graph properties, and the $k$-sat problem
• Closure properties of constraints
• Hunting for sharp thresholds
• Models for Random Constraint Satisfaction Problems
• The complexity of satisfiability problems
• Random constraint satisfaction: A more accurate picture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item