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

Simple item page
dc.creatorLi, Kang
dc.creatorMa, Hui
dc.creatorZhou, Haijun
dc.date2008-09-25
dc.date2009-03-17
dc.date.accessioned2026-07-07T12:52:34Z
dc.date.available2026-07-07T12:52:34Z
dc.descriptionA 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.
dc.description13 pages, 6 figures. Final version as published in PRE
dc.identifierhttps://arxiv.org/abs/0809.4332
dc.identifierhttp://arxiv.org/abs/0809.4332
dc.identifierPhysical Review E 79, 031102 (2009)
dc.identifierdoi:10.1103/PhysRevE.79.031102
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/223336
dc.subjectDisordered Systems and Neural Networks
dc.subjectComputational Complexity
dc.titleFrom one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
dc.typetext

Files

Collections

arXiv