The Phase Diagram of 1-in-3 Satisfiability Problem

Details The Phase Diagram of 1-in-3 Satisfiability Problem The Phase Diagram of 1-in-3 Satisfiability Problem

2007-02-26

arxiv.org/abs/cond-mat/0702610v2

Phys. Rev. E 76, 011101 (2007)

Physics

Condensed Matter

Statistical Mechanics

30 pages, 12 figures

Scientific paper

10.1103/PhysRevE.76.011101

We study the 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 the 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.

Affiliated with

Also associated with

No associations

Rating

The Phase Diagram of 1-in-3 Satisfiability Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Phase Diagram of 1-in-3 Satisfiability Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Phase Diagram of 1-in-3 Satisfiability Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131443