Entropy of theK-Satisfiability Problem

DOI10.1103/PHYSREVLETT.76.3881MaRDI QIDQ4492386zbMATH OpenOpenAlexWikidataFDO

Authors Riccardo Zecchina, R. Monasson

Publication date 16 July 2000

Published in Physical Review Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9603014, http://link.aps.org/abstract/PRL/v76/p3881

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Sensitivity, stability, parametric optimization (90C31)

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 $Kgeq3$.

Recommendations

• scientific article; zbMATH DE number 2012168
• The Complexity of Approximating the Entropy
• Kolmogorov entropy in the context of computability theory
• A note on Kolmogorov complexity and entropy
• scientific article; zbMATH DE number 2182449
• Entropy measures vs. Kolmogorov complexity
• Entropy and the complexity of graphs revisited
• Entropic exercises around the Kneser–Poulsen conjecture
• Entropy and the combinatorial dimension
• An entropy proof of the Kahn-Lovász theorem

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Counting the number of solutions for instances of satisfiability
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Optimization by simulated annealing
• Tail bounds for occupancy and the satisfiability threshold conjecture

Cited in

(25)

• A framework for structured quantum search.
• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Quantum dynamics of a harmonic oscillator in a deformed Bath in the presence of Lamb shift
• Belief propagation on the random \(k\)-SAT model
• On the freezing of variables in random constraint satisfaction problems
• The scaling window of the 2-SAT transition
• Criticality and heterogeneity in the solution space of random constraint satisfaction problems
• Rényi entropies as a measure of the complexity of counting problems
• A spin glass approach to the directed feedback vertex set problem
• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Directed dominating set problem studied by cavity method: warning propagation and population dynamics
• On the survey-propagation equations in random constraint satisfiability problems
• Phase Transition in the Number Partitioning Problem
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• A hard-sphere model on generalized Bethe lattices: dynamics
• Statistical and algebraic analysis of a family of random Boolean equations
• The K-SAT problem in a simple limit
• Statistical mechanics methods and phase transitions in optimization problems
• Rigorous results for random (2+p)-SAT
• Random 2-SAT: Results and problems
• The number of satisfying assignments of random 2‐SAT formulas
• Biased random k‐SAT
• The number of random 2-SAT solutions is asymptotically log-normal
• Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation
• The asymptotic k-SAT threshold

This page was built for publication: Entropy of theK-Satisfiability Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4492386)