Access Restriction

Author Angione, Claudio ♦ Occhipinti, Annalisa ♦ Nicosia, Giuseppe
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Bose-Einstein distribution ♦ Maxwell-Boltzmann distribution ♦ SAT ♦ SAT solvers ♦ Complex network ♦ Phase transition ♦ Physics-inspired computation ♦ Quantum and classical system
Abstract Recent studies in theoretical computer science have exploited new algorithms and methodologies based on statistical physics for investigating the structure and the properties of the Satisfiability (SAT) problem. We propose a characterization of the SAT problem as a physical system, using both quantum and classical statistical-physical models. We associate a graph to an SAT instance and we prove that a Bose-Einstein condensation occurs in the instance with higher probability if the quantum distribution is adopted in the generation of the graph. Conversely, the fit-get-rich behavior is more likely if we adopt the Maxwell-Boltzmann distribution. Our method allows a comprehensive analysis of the SAT problem based on a new definition of entropy of an instance, without requiring the computation of its truth assignments. The entropy of an SAT instance increases in the satisfiability region as the number of free variables in the instance increases. Finally, we develop six new solvers for the MaxSAT problem based on quantum and classical statistical distributions, and we test them on random SAT instances, with competitive results. We experimentally prove that the performance of the solvers based on the two distributions depends on the criterion used to flag clauses as satisfied in the SAT solving process.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-01-07
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 19
Page Count 15
Starting Page 1.1
Ending Page 1.15

Open content in new tab

   Open content in new tab
Source: ACM Digital Library