Entropy of theK-Satisfiability Problem

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

Mathematics Subject Classification ID

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

Related Items (23)

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

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