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.

arXiv commentDuring the PRE review process

References in corpus (25)

• 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
• Clustering of solutions in the random satisfiability problem
• Statistical mechanics of the random K-SAT model
• The Entropy of the K-Satisfiability Problem
• Identifying optimal targets of network attack by belief propagation
• Learning by message-passing in networks of discrete synapses
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Spin glass approach to the feedback vertex set problem
• 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
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Entropy landscape of solutions in the binary perceptron problem
• Biased landscapes for random Constraint Satisfaction Problems
• 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
• 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
• Finite-size scaling in random $K$-satisfiability problems

Cited by in corpus (4)

• Optimization of the dynamic transition in the continuous coloring problem
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Interacting Copies of Random Constraint Satisfaction Problems