An exactly solvable random satisfiability problem

DOI10.1088/0305-4470/35/36/301zbMATH Open1095.68041arXivcond-mat/0206352OpenAlexW3099461015MaRDI QIDQ4467964FDOQ4467964

Authors: Andrea Sportiello, Sergio Caracciolo 

Publication date: 10 June 2004

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Abstract: We 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.

Full work available at URL: https://arxiv.org/abs/cond-mat/0206352

Recommendations

• Rigorous results for random (\(2+p)\)-SAT
• A probabilistic study on the satisfiability problem
• scientific article; zbMATH DE number 1448978
• Phase coexistence and finite-size scaling in random combinatorial problems
• Theory and Applications of Satisfiability Testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exactly solvable models; Bethe ansatz (82B23)

This page was built for publication: An exactly solvable random satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4467964)