Spines of random constraint satisfaction problems: definition and connection with computational complexity

DOI10.1007/s10472-005-7033-2zbMath1086.68055arXivcs/0503082OpenAlexW2137376285WikidataQ62599716 ScholiaQ62599716MaRDI QIDQ812393

Stefan Boettcher, Allon G. Percus, Gabriel I. Istrate

Publication date: 23 January 2006

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0503082

zbMATH Keywords

phase transitionsspineconstraint satisfaction problemsresolution complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Critical phenomena in equilibrium statistical mechanics (82B27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Biased random k‐SAT ⋮ A parametric worst-case approach to fairness in cooperative games with transferable utility ⋮ Geometric properties of satisfying assignments of random ε-1-in-kSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Nature's way of optimizing
• On the weak pigeonhole principle
• The Efficiency of Resolution and Davis--Putnam Procedures
• Coloring Random Graphs
• Many hard examples for resolution
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• Short proofs are narrow—resolution made simple
• Extremal optimization of graph partitioning at the percolation threshold
• Statistical mechanics methods and phase transitions in optimization problems
• Frozen development in graph coloring