Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem

Abstract

Shortened abstract: A mean field theory of long range frustration is constructed for spin glass systems with quenched randomness of vertex--vertex connections and of spin--spin coupling strengths. This theory is applied to a spin glass model of the random $K$-satisfiability problem (K=2 or K=3). The zero--temperature phase diagram of the $\pm J$ Viana--Bray model is also determined, which is identical to that of the random 2-SAT problem. The predicted phase transition between a non-frustrated and a long--rangely frustrated spin glass phase might also be observable in real materials at a finite temperature.

Final version. Published in New Journal of Physics, freely available at http://www.njp.org/

References in corpus (6)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Higher-order QED corrections to single-W production in electron-positron collisions
• Maximum matching on random graphs

Cited by in corpus (11)

• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• The network source location problem: ground state energy, entropy and effects of freezing
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations