Statistical mechanics of the random K-satisfiability model

Rémi Monasson and Riccardo Zecchina
Phys. Rev. E 56, 1357 – Published 1 August 1997
PDFExport Citation

Abstract

The random K-satisfiability problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=αN random logical clauses containing K variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest K=2, K>~3, and K1. The calculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case K=2, the (rigorously known) critical value (α=1) of the number of clauses per Boolean variable is recovered while for K>~3 we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large K.

  • Received 24 June 1996

DOI:https://doi.org/10.1103/PhysRevE.56.1357

©1997 American Physical Society

Authors & Affiliations

Rémi Monasson1 and Riccardo Zecchina

  • 1Laboratoire de Physique Théorique de l’ENS, 24 rue Lhomond, 75231 Paris Cedex 05, France
  • 2Dipartimento di Fisica, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy

References (Subscription Required)

Click to Expand
Issue

Vol. 56, Iss. 2 — August 1997

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×