An exactly solvable random satisfiability problem

Simple item page
dc.creatorCaracciolo, Sergio
dc.creatorSportiello, Andrea
dc.date2002-06-18
dc.date.accessioned2026-07-07T10:48:06Z
dc.date.available2026-07-07T10:48:06Z
dc.descriptionWe introduce a new model for the generation of random satisfiability problems. It is an extension of the hyper-SAT model of Ricci-Tersenghi, Weigt and Zecchina, which is a variant of the famous K-SAT model: it is extended to q-state variables and relates to a different choice of the statistical ensemble. The model has an exactly solvable statistic: the critical exponents and scaling functions of the SAT/UNSAT transition are calculable at zero temperature, with no need of replicas, also with exact finite-size corrections. We also introduce an exact duality of the model, and show an analogy of thermodynamic properties with the Random Energy Model of disordered spin systems theory. Relations with Error-Correcting Codes are also discussed.
dc.description31 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/cond-mat/0206352
dc.identifierhttp://arxiv.org/abs/cond-mat/0206352
dc.identifierJ.Phys.A35:7661-7688,2002
dc.identifierdoi:10.1088/0305-4470/35/36/301
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/183759
dc.subjectStatistical Mechanics
dc.subjectDisordered Systems and Neural Networks
dc.subjectHigh Energy Physics - Lattice
dc.titleAn exactly solvable random satisfiability problem
dc.typetext

Files

Collections

arXiv