Exhaustive enumeration unveils clustering and freezing in random 3-SAT

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.
4 pages, 3 figures

Keywords

Statistical Mechanics, Disordered Systems and Neural Networks, Computational Complexity, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/170350

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0804.0362
 http://arxiv.org/abs/0804.0362
 Phys. Rev. E 78, 040101(R) (2008)
 doi:10.1103/PhysRevE.78.040101

Collections

arXiv