Entropy of theK-Satisfiability Problem
From MaRDI portal
Publication:4492386
DOI10.1103/PhysRevLett.76.3881zbMath1042.82567arXivcond-mat/9603014OpenAlexW2158907280WikidataQ74567747 ScholiaQ74567747MaRDI QIDQ4492386
Riccardo Zecchina, Remi 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
Sensitivity, stability, parametric optimization (90C31) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)
Related Items
Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation, Unnamed Item, Quantum dynamics of a harmonic oscillator in a deformed Bath in the presence of Lamb shift, The number of satisfying assignments of random 2‐SAT formulas, Biased random k‐SAT, The asymptotic \(k\)-SAT threshold, The scaling window of the 2-SAT transition, 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, On the freezing of variables in random constraint satisfaction problems, Statistical mechanics methods and phase transitions in optimization problems, Rigorous results for random (\(2+p)\)-SAT, Random 2-SAT: Results and problems, CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS, On the survey-propagation equations in random constraint satisfiability problems, A hard-sphere model on generalized Bethe lattices: dynamics, Statistical and algebraic analysis of a family of random Boolean equations, Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics, Belief propagation on the random \(k\)-SAT model, A framework for structured quantum search., Phase Transition in the Number Partitioning Problem, Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
Cites Work
- Optimization by Simulated Annealing
- 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
- Tail bounds for occupancy and the satisfiability threshold conjecture
