$T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem

Abstract

During the past decade, phase-transition phenomena in the random 3-satisfiability (3-SAT) problem has been intensively studied by statistical physics methods. In this work, we study the random 3-SAT problem by the mean-field first-step replica-symmetry-broken cavity theory at the limit of temperature $T\to 0$. The reweighting parameter $y$ of the cavity theory is allowed to approach infinity together with the inverse temperature $\beta$ with fixed ratio $r=y/\beta$. Focusing on the the system's space of satisfiable configurations, we carry out extensive population dynamics simulations using the technique of importance sampling and we obtain the entropy density $s(r)$ and complexity $\Sigma (r)$ of zero-energy clusters at different $r$ values. We demonstrate that the population dynamics may reach different fixed points with different types of initial conditions. By knowing the trends of $s(r)$ and $\Sigma (r)$ with $r$, we can judge whether a certain type of initial condition is appropriate at a given $r$ value. This work complements and confirms the results of several other very recent theoretical studies.

10 pages with 5 figures. Extensively revised. PRE published version

References in corpus (17)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• Statistical mechanics of the random K-SAT model
• The Entropy of the K-Satisfiability Problem
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Landscape of solutions in constraint satisfaction problems
• Message passing for vertex covers
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Clustering of solutions in hard satisfiability problems
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Distribution of equilibrium free energies in a thermodynamic system with broken ergodicity

Cited by in corpus (11)

• Entropy landscape of solutions in the binary perceptron problem
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Spin glass phase transitions in the random feedback vertex set problem
• Maximally flexible solutions of a random $K$-satisfiability formula
• Spin-glass model for the C-dismantling problem
• The network source location problem: ground state energy, entropy and effects of freezing
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations