Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations

Abstract

The random K-satisfiability (K-SAT) problem is an important problem for studying typical-case complexity of NP-complete combinatorial satisfaction; it is also a representative model of finite-connectivity spin-glasses. In this paper we review our recent efforts on the solution space fine structures of the random K-SAT problem. A heterogeneity transition is predicted to occur in the solution space as the constraint density alpha reaches a critical value alpha_cm. This transition marks the emergency of exponentially many solution communities in the solution space. After the heterogeneity transition the solution space is still ergodic until alpha reaches a larger threshold value alpha_d, at which the solution communities disconnect from each other to become different solution clusters (ergodicity-breaking). The existence of solution communities in the solution space is confirmed by numerical simulations of solution space random walking, and the effect of solution space heterogeneity on a stochastic local search algorithm SEQSAT, which performs a random walk of single-spin flips, is investigated. The relevance of this work to glassy dynamics studies is briefly mentioned.

11 pages, 4 figures. Final version as will appear in Journal of Physics: Conference Series (Proceedings of the International Workshop on Statistical-Mechanical Informatics, March 7-10, 2010, Kyoto, Japan)

References in corpus (11)

• Supercooled Liquids for Pedestrians
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Clustering analysis of the ground-state structure of the vertex-cover problem
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula

Cited by in corpus (1)

• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems