Phase diagram of the 1-in-3 satisfiability problem

Jack Raymond*, Andrea Sportiello, Lenka Zdeborová

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Article number011101
JournalPhysical Review E
Volume76
Issue number1
DOIs
Publication statusPublished - 2 Jul 2007

Fingerprint

Satisfiability Problem
Phase Diagram
Connectivity
phase diagrams
cavities
Ensemble
replicas
Cavity Method
broken symmetry
polynomials
Replica
intervals
Symmetry Breaking
Structural Properties
Polynomial time
Cavity
predictions
Interpolate
Cover
Interval

Bibliographical note

©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

Cite this

Raymond, J., Sportiello, A., & Zdeborová, L. (2007). Phase diagram of the 1-in-3 satisfiability problem. Physical Review E, 76(1), [011101]. https://doi.org/10.1103/PhysRevE.76.011101
Raymond, Jack ; Sportiello, Andrea ; Zdeborová, Lenka. / Phase diagram of the 1-in-3 satisfiability problem. In: Physical Review E. 2007 ; Vol. 76, No. 1.
@article{02b66908b1f740acb4fc29b9d4d66622,
title = "Phase diagram of the 1-in-3 satisfiability problem",
abstract = "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.",
author = "Jack Raymond and Andrea Sportiello and Lenka Zdeborov{\'a}",
note = "{\circledC}2007 The American Physical Society. Phase diagram of the 1-in-3 satisfiability problem Jack Raymond, Andrea Sportiello, and Lenka Zdeborov{\'a} Phys. Rev. E 76, 011101 – Published 2 July 2007",
year = "2007",
month = "7",
day = "2",
doi = "10.1103/PhysRevE.76.011101",
language = "English",
volume = "76",
journal = "Physical Review E",
issn = "1539-3755",
publisher = "American Physical Society",
number = "1",

}

Raymond, J, Sportiello, A & Zdeborová, L 2007, 'Phase diagram of the 1-in-3 satisfiability problem', Physical Review E, vol. 76, no. 1, 011101. https://doi.org/10.1103/PhysRevE.76.011101

Phase diagram of the 1-in-3 satisfiability problem. / Raymond, Jack; Sportiello, Andrea; Zdeborová, Lenka.

In: Physical Review E, Vol. 76, No. 1, 011101, 02.07.2007.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Phase diagram of the 1-in-3 satisfiability problem

AU - Raymond, Jack

AU - Sportiello, Andrea

AU - Zdeborová, Lenka

N1 - ©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

PY - 2007/7/2

Y1 - 2007/7/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34547297161&partnerID=8YFLogxK

UR - https://arxiv.org/pdf/cond-mat/0702610.pdf

U2 - 10.1103/PhysRevE.76.011101

DO - 10.1103/PhysRevE.76.011101

M3 - Article

AN - SCOPUS:34547297161

VL - 76

JO - Physical Review E

JF - Physical Review E

SN - 1539-3755

IS - 1

M1 - 011101

ER -