From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy

Details From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy

2008-09-25

arxiv.org/abs/0809.4332v3

Physical Review E 79, 031102 (2009)

Physics

Condensed Matter

Disordered Systems and Neural Networks

13 pages, 6 figures. Final version as published in PRE

Scientific paper

10.1103/PhysRevE.79.031102

A solution to a 3-satisfiability (3-SAT) formula can be expanded into a cluster, all other solutions of which are reachable from this one through a sequence of single-spin flips. Some variables in the solution cluster are frozen to the same spin values by one of two different mechanisms: frozen-core formation and long-range frustrations. While frozen cores are identified by a local whitening algorithm, long-range frustrations are very difficult to trace, and they make an entropic belief-propagation (BP) algorithm fail to converge. For BP to reach a fixed point the spin values of a tiny fraction of variables (chosen according to the whitening algorithm) are externally fixed during the iteration. From the calculated entropy values, we infer that, for a large random 3-SAT formula with constraint density close to the satisfiability threshold, the solutions obtained by the survey-propagation or the walksat algorithm belong neither to the most dominating clusters of the formula nor to the most abundant clusters. This work indicates that a single solution cluster of a random 3-SAT formula may have further community structures.

Affiliated with

Also associated with

No associations

Rating

From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy 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 From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181563