The SAT-UNSAT transition for random constraint satisfaction problems
From MaRDI portal
Publication:1025462
DOI10.1016/J.DISC.2008.04.025zbMath1185.68639OpenAlexW2047532073MaRDI QIDQ1025462
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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (4)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: The SAT-UNSAT transition for random constraint satisfaction problems
