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

Area of Science:

• Condensed Matter Physics
• Computational Physics
• Statistical Mechanics

Background:

• Spin glasses are complex magnetic systems with disordered interactions.
• Understanding their energy landscapes is crucial for predicting their behavior.
• Greedy algorithms offer a computational approach to explore these landscapes.

Purpose of the Study:

• To investigate the energy landscapes of two distinct spin glass models.
• To evaluate the efficiency of the Gmax greedy algorithm in approaching ground-state energy densities.
• To compare the performance of Gmax on different spin glass models.

Main Methods:

• Utilized a greedy single-spin flipping process, Gmax.
• Applied Gmax to the random maximum two-satisfiability problem.
• Applied Gmax to the ±J Viana-Bray spin glass model.
• Analyzed the energy density evolution over time.

Main Results:

• Gmax efficiently approaches the ground-state energy density for the random satisfiability problem.
• Energy density decreases with time as e(t)-e(∞)=h(log(10)t)(-z), indicating funnel-shaped energy landscapes.
• Gmax becomes trapped in local minima for the ±J Viana-Bray model, highlighting model-specific dynamics.

Conclusions:

• The Gmax algorithm demonstrates efficiency in exploring certain spin glass energy landscapes.
• The dynamics of spin glasses significantly influence the effectiveness of greedy exploration algorithms.
• Energy landscape topography, characterized by funnel regions, impacts algorithmic performance.