Phase diagram of the 1-in-3 satisfiability problem


We study typical case properties of the 1-in-3 satisfiability problem, the Boolean satisfaction problem, where a clause is satisfied by exactly one literal, in an enlarged random ensemble parametrized by average connectivity and probability of negation of a variable in a clause. Random 1-in-3 satisfiability and exact 3-cover are special cases of this ensemble. We interpolate between these cases from a region where satisfiability can be typically decided for all connectivities in polynomial time to a region where deciding satisfiability is hard, in some interval of connectivities. We derive several rigorous results in the first region and develop a one-step replica-symmetry-breaking cavity analysis in the second one. We discuss the prediction for the transition between the almost surely satisfiable and the almost surely unsatisfiable phase, and other structural properties of the phase diagram, in light of cavity method results.

Publication DOI:
Divisions: College of Engineering & Physical Sciences
Additional Information: ©2007 The American Physical Society. Phase diagram of the 1-in-3 satisfiability problem Jack Raymond, Andrea Sportiello, and Lenka Zdeborová Phys. Rev. E 76, 011101 – Published 2 July 2007
Uncontrolled Keywords: Physics and Astronomy(all),Condensed Matter Physics,Statistical and Nonlinear Physics,Mathematical Physics
Publication ISSN: 1550-2376
Last Modified: 23 Apr 2024 07:10
Date Deposited: 03 Dec 2018 15:27
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
https://arxiv.o ... mat/0702610.pdf (Author URL)
PURE Output Type: Article
Published Date: 2007-07-02
Authors: Raymond, Jack
Sportiello, Andrea
Zdeborová, Lenka



Version: Published Version

| Preview

Export / Share Citation


Additional statistics for this record