Clustering of solutions in the random satisfiability problem

Simple item page
dc.creatorMezard, M.
dc.creatorMora, T.
dc.creatorZecchina, R.
dc.date2005-04-04
dc.date.accessioned2026-07-07T03:04:25Z
dc.date.available2026-07-07T03:04:25Z
dc.descriptionUsing elementary rigorous methods we prove the existence of a clustered phase in the random $K$-SAT problem, for $K\geq 8$. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.
dc.description4 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/cond-mat/0504070
dc.identifierhttp://arxiv.org/abs/cond-mat/0504070
dc.identifierPhys. Rev. Lett. 94, 197205 (2005)
dc.identifierdoi:10.1103/PhysRevLett.94.197205
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/26130
dc.subjectDisordered Systems and Neural Networks
dc.subjectComputational Complexity
dc.titleClustering of solutions in the random satisfiability problem
dc.typetext

Files

Collections

arXiv