Simplest random K-satisfiability problem

Abstract

We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of $\gamma N$ random boolean constraints which are to be satisfied simultaneously by $N$ logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While such problems become extraordinarily hard to solve by local search methods in a large region of the parameter space, still at least one solution may be superimposed by construction. The statistical properties of the model can be studied exactly by the replica method and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical/topological structures responsible for dynamic and static phase transitions as well as for the onset of computational complexity in local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterization of the critical scaling behaviour.

14 pages, 5 figures, to appear in Phys. Rev. E (Feb 2001). v2: minor errors and references corrected

Cited by in corpus (72)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Statistical physics of inference: Thresholds and algorithms
• Coloring random graphs
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A ferromagnet with a glass transition
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Exact solutions for diluted spin glasses and optimization problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• On the dynamics of the glass transition on Bethe lattices
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Replica bounds for diluted non-Poissonian spin systems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Glassy Phase of Optimal Quantum Control
• The high temperature region of the Viana-Bray diluted spin glass model
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• On the sufficiency of pairwise interactions in maximum entropy models of biological networks
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Phase coexistence and finite-size scaling in random combinatorial problems
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Geometrical organization of solutions to random linear Boolean equations
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• Improved extremal optimization for the Ising spin glass
• On the stochastic dynamics of disordered spin models
• Statistical mechanics of the vertex-cover problem
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• A microscopic description of the aging dynamics: fluctuation-dissipation relations, effective temperature and heterogeneities
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Jamming Model for the Extremal Optimization Heuristic
• Grassmann Integral Representation for Spanning Hyperforests
• On random graphs and the statistical mechanics of granular matter
• Glassy aspects of melting dynamics (On melting dynamics and the glass transition, Part I)
• Glassy dynamics in granular compaction: sand on random graphs
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Aging dynamics of heterogeneous spin models
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• Statistical mechanics of error exponents for error-correcting codes
• Bicoloring Random Hypergraphs
• Approximate analysis of search algorithms with "physical" methods
• Thermodynamics of spin systems on small-world hypergraphs
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Entanglement phase transition with spin glass criticality
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Boundary conditions dependence of the phase transition in the quantum Newman-Moore model
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Belief-Propagation Guided Monte-Carlo Sampling
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Obstacles to quantum annealing in a planar embedding of XORSAT
• Statistical mechanics methods and phase transitions in optimization problems
• Replica symmetry breaking for Ulam's problem
• The Random-Diluted Triangular Plaquette Model: study of phase transitions in a Kinetically Constrained Model
• Dynamics of sparse Boolean networks with multi-node and self-interactions
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Phase Transitions and all that
• Realizing interdependent couplings as thermal or higher-order interactions
• An exactly solvable random satisfiability problem
• A simple one dimensional glassy Kac model
• General duality for abelian-group-valued statistical-mechanics models
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Qubit Vitrification and Entanglement Criticality on a Quantum Simulator
• Competition and cooperation:aspects of dynamics in sandpiles
• Tensor networks for $p$-spin models
• Entropy and chirality in sphinx tilings
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem