Random subcubes as a toy model for constraint satisfaction problems

Abstract

We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.

21 pages, 4 figures

References in corpus (18)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Clustering of solutions in the random satisfiability problem
• Lattice Glass Models
• A Landscape Analysis of Constraint Satisfaction Problems
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• The glassy phase of Gallager codes
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Landscape of solutions in constraint satisfaction problems
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Chaotic temperature dependence in a model of spin glasses
• Geometrical organization of solutions to random linear Boolean equations

Cited by in corpus (14)

• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Catching the k-NAESAT Threshold
• High q-State Clock Spin Glasses in Three Dimensions and the Lyapunov Exponents of Chaotic Phases and Chaotic Phase Boundaries
• Overfrustrated and Underfrustrated Spin-Glasses in d=3 and 2: Evolution of Phase Diagrams and Chaos Including Spin-Glass Order in d=2
• A solvable model of quantum random optimization problems
• The Chiral Potts Spin Glass in d=2 and 3 Dimensions
• Phase Transitions between Different Spin-Glass Phases and between Different Chaoses in Quenched Random Chiral Systems
• Devil's Staircase Continuum in the Chiral Clock Spin Glass with Competing Ferromagnetic-Antiferromagnetic and Left-Right Chiral Interactions
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Revisiting the replica trick: Competition between spin glass and conventional order
• The effect of quantum fluctuations on the coloring of random graphs
• Chaotic Spin Correlations in Frustrated Ising Hierarchical Lattices