Maximally flexible solutions of a random $K$-satisfiability formula

Abstract

Random $K$-satisfiability ($K$-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random $K$-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single $K$-SAT instances.

During the PRE review process

References in corpus (10)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems