Locked constraint satisfaction problems

Abstract

We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.

4 pages, 2 figures

References in corpus (11)

• 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
• 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
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations

Cited by in corpus (36)

• Adiabatic Quantum Computing
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Origin of the computational hardness for learning with binary synapses
• Constraint satisfaction problems with isolated solutions are hard
• Storage capacity in symmetric binary perceptrons
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Degeneracy, degree, and heavy tails in quantum annealing
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Static properties of 2D spin-ice as a sixteen-vertex model
• Numerical Solution-Space Analysis of Satisfiability Problems
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• On the Atypical Solutions of the Symmetric Binary Perceptron
• (Dis)assortative Partitions on Random Regular Graphs
• Dynamical mean field theory for models of confluent tissues and beyond
• Approximating random quantum optimization problems
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Statistical mechanics of the maximum-average submatrix problem
• Message passing algorithms for the Hopfield network reconstruction: threshold behavior and limitation
• The effect of quantum fluctuations on the coloring of random graphs
• Susceptibility Propagation for Constraint Satisfaction Problems
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Typical case behaviour of spin systems in random graph and composite ensembles
• Decimation flows in constraint satisfaction problems
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm