Satisfiability Thresholds for Regular Occupation Problems
arXiv:1811.00991 · doi:10.1017/S0963548324000440
Abstract
In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems. The regular -in- occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the -in- occupation problem has been rigorously established. Here we determine the satisfiability threshold of the -in- occupation problem for all . In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignements to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.
arXiv comment40 pages, 3 figures, major updated: threshold established for all arities
References in corpus (12)
- Information-theoretic thresholds from the cavity method
- The asymptotic -SAT threshold
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Constraint satisfaction problems with isolated solutions are hard
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Charting the replica symmetric phase
- Phase transitions in the -coloring of random hypergraphs
- Bicoloring Random Hypergraphs
- The Phase Transition in Exact Cover
- Planting colourings silently
- Circular Coloring of Random Graphs: Statistical Physics Investigation
- Susceptibility Propagation for Constraint Satisfaction Problems