Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process

Abstract

In this brief report we explore the energy landscapes of two spin glass models using a greedy single-spin flipping process, {\tt Gmax}. The ground-state energy density of the random maximum two-satisfiability problem is efficiently approached by {\tt Gmax}. The achieved energy density $e(t)$ decreases with the evolution time $t$ as $e(t)-e(\infty )=h({\log }_{10}t{)}^{-z}$ with a small prefactor $h$ and a scaling coefficient $z>1$, indicating an energy landscape with deep and rugged funnel-shape regions. For the $\pm J$ Viana-Bray spin glass model, however, the greedy single-spin dynamics quickly gets trapped to a local minimal region of the energy landscape.

5 pages with 4 figures included. Accepted for publication in Physical Review E as a brief report

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Circumspect descent prevails in solving random constraint satisfaction problems
• Statistical Mechanics of maximal independent sets
• Energy-landscape network approach to the glass transition
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems

Cited by in corpus (1)

• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking