Constraint satisfaction problems with isolated solutions are hard

Abstract

We study the phase diagram and the algorithmic hardness of the random `locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of boolean formulas or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.

19 pages, 12 figures

References in corpus (28)

• 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
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Reconstruction on trees and spin glass transition
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• The number of matchings in random graphs
• Glass models on Bethe lattices
• Learning by message-passing in networks of discrete synapses
• Survey Propagation as local equilibrium equations
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Survey-propagation decimation through distributed local computations
• Locked constraint satisfaction problems
• Robust reconstruction on trees is determined by the second eigenvalue
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Potts Glass on Random Graphs
• Geometrical organization of solutions to random linear Boolean equations
• Random multi-index matching problems
• On the number of circuits in random graphs
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• A frozen glass phase in the multi-index matching problem
• Bicoloring Random Hypergraphs

Cited by in corpus (35)

• Adiabatic Quantum Computing
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Origin of the computational hardness for learning with binary synapses
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Typology of phase transitions in Bayesian inference problems
• Storage capacity in symmetric binary perceptrons
• Fast counting with tensor networks
• Spectral Detection on Sparse Hypergraphs
• Collaboration in Social Networks
• Entropy landscape of solutions in the binary perceptron problem
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• 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
• On the role of synaptic stochasticity in training low-precision neural networks
• The large deviations of the whitening process in random constraint satisfaction problems
• On the Atypical Solutions of the Symmetric Binary Perceptron
• (Dis)assortative Partitions on Random Regular Graphs
• Learning by random walks in the weight space of the Ising perceptron
• Next nearest neighbour Ising models on random graphs
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The network source location problem: ground state energy, entropy and effects of freezing
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Susceptibility Propagation for Constraint Satisfaction Problems
• Decimation flows in constraint satisfaction problems
• Satisfiability Thresholds for Regular Occupation Problems
• Computing a Knot Invariant as a Constraint Satisfaction Problem
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem