The Entropy of the K-Satisfiability Problem

Abstract

The threshold behaviour of the K-Satisfiability problem is studied in the framework of the statistical mechanics of random diluted systems. We find that at the transition the entropy is finite and hence that the transition itself is due to the abrupt appearance of logical contradictions in all solutions and not to the progressive decreasing of the number of these solutions down to zero. A physical interpretation is given for the different cases $K=1$, $K=2$ and $K\ge 3$.

revtex, 11 pages + 1 figure

Cited by in corpus (80)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Statistical physics of inference: Thresholds and algorithms
• The Scaling Window of the 2-SAT Transition
• Statistical mechanics of the random K-SAT model
• Phase Transition in the Number Partitioning Problem
• Marginally Stable Equilibria in Critical Ecosystems
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Learning by message-passing in networks of discrete synapses
• Simplest random K-satisfiability problem
• Exact solutions for diluted spin glasses and optimization problems
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Probabilistic Analysis of the Number Partitioning Problem
• The asymptotic $k$-SAT threshold
• Tricritical Points in Random Combinatorics: the (2+p)-SAT case
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Matrix Games, Mixed Strategies, and Statistical Mechanics
• Phase coexistence and finite-size scaling in random combinatorial problems
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Relaxation in graph coloring and satisfiability problems
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• A backtracking survey propagation algorithm for K-satisfiability
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Time scale separation and heterogeneous off-equilibrium dynamics in spin models over random graphs
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Counting good truth assignments of random k-SAT formulae
• Statistical mechanics of random two-player games
• A Framework for Structured Quantum Search
• Entropy and typical properties of Nash equilibria in two-player games
• The energy landscape networks of spin-glasses
• Computation of the Kolmogorov-Sinai entropy using statistitical mechanics: Application of an exchange Monte Carlo method
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Influence of the Ground-State Topology on the Domain-Wall Energy in the Edwards-Anderson +/- J Spin Glass Model
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Quantum Adiabatic Algorithm and Large Spin Tunnelling
• Numerical Solution-Space Analysis of Satisfiability Problems
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• The random 2-SAT partition function
• A hard-sphere model on generalized Bethe lattices: Statics
• Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
• Some remarks on the survey decimation algorithm for K-satisfiability
• Quantum adiabatic optimization and combinatorial landscapes
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Solution-space structure of (some) optimization problems
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• On the survey-propagation equations for the random K-satisfiability problem
• Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach
• Renyi entropies as a measure of the complexity of counting problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Small-world hypergraphs on a bond-disordered Bethe lattice
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Local Search Methods for Quantum Computers
• Counting solutions from finite samplings
• A spin glass approach to the directed feedback vertex set problem
• A hard-sphere model on generalised Bethe lattices: Dynamics
• What makes a phase transition? Analysis of the random satisfiability problem
• Biased random satisfiability problems: From easy to hard instances
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• On the behaviour of random K-SAT on trees
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• Optimization and Physics: On the satisfiability of random Boolean formulae
• Total suppression of a large spin tunneling barrier in quantum adiabatic computation
• Spanning Trees in Random Satisfiability Problems
• Phase transitions in Number Theory: from the Birthday Problem to Sidon Sets
• Witness of unsatisfiability for a random 3-satisfiability formula
• A Framework for Quantum Search Heuristics
• Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem
• Biased random k-SAT
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem