Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

DOI10.1016/j.ipl.2011.07.006zbMath1260.68166OpenAlexW2030218034MaRDI QIDQ1944183

Chunyan Zhao, Zhi Ming Zheng

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.07.006

zbMATH Keywords

computational complexityphase transitionconstraint satisfaction problemthreshold behaviorfinite-size scalingmodel RB

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

Cites Work

• Unnamed Item
• Unnamed Item
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Random 2-SAT and unsatisfiability
• A remark on random 2-SAT
• Many hard examples in exact phase transitions
• The scaling window of the 2-SAT transition
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Threshold values of random K‐SAT from the cavity method
• The complexity of theorem-proving procedures

This page was built for publication: Threshold behaviors of a random constraint satisfaction problem with exact phase transitions