Spines of random constraint satisfaction problems: definition and connection with computational complexity
From MaRDI portal
Publication:812393
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
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