{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:04Z","timestamp":1750306684417,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2629498","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T14:39:29Z","timestamp":1410273569000},"source":"Crossref","is-referenced-by-count":0,"title":["Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions"],"prefix":"10.1145","volume":"19","author":[{"given":"Claudio","family":"Angione","sequence":"first","affiliation":[{"name":"Computer Laboratory, University of Cambridge, UK"}]},{"given":"Annalisa","family":"Occhipinti","sequence":"additional","affiliation":[{"name":"Computer Laboratory, University of Cambridge, UK"}]},{"given":"Giuseppe","family":"Nicosia","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science - University of Catania and Institute for Advanced Studies, Italy"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680382"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0712263105"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.11.039"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14186-7_3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011300624424"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.5632"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69149-5_27"},{"key":"e_1_2_1_8_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms. MIT Press.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/035"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216581"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.06.066"},{"volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 499--504","author":"Hamadi Y.","key":"e_1_2_1_12_1"},{"volume":"16","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Kautz H.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aop.2006.08.002"},{"volume-title":"Constraint Satisfaction Networks in Physics and Computation. Clarendon Press","year":"2007","author":"M\u00e9zard M.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jphysparis.2009.05.013"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard G. Parisi and R. Zecchina. 2002. Analytic and algorithmic solution of random satisfiability problems. Science 297 5582 (2002) 812--815.  M. M\u00e9zard G. Parisi and R. Zecchina. 2002. Analytic and algorithmic solution of random satisfiability problems. Science 297 5582 (2002) 812--815.","DOI":"10.1126\/science.1073287"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence. AAAI Press\/MIT Press, 459--465","author":"Mitchell D.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"R. Monasson R. Zecchina S. Kirkpatrick B. Selman and L. Troyansky. 1999. Determining computational complexity from characteristic phase transitions. Nature 400 6740 (1999) 133--137.  R. Monasson R. Zecchina S. Kirkpatrick B. Selman and L. Troyansky. 1999. Determining computational complexity from characteristic phase transitions. Nature 400 6740 (1999) 133--137.","DOI":"10.1038\/22055"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2005.05.063"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(97)00294-4"},{"key":"e_1_2_1_22_1","unstructured":"R. K. Pathria. 1996. Statistical Mechanics. Butterworth-Heinemann.  R. K. Pathria. 1996. Statistical Mechanics. Butterworth-Heinemann."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.104.576"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"C. J. Pethick and H. Smith. 2001. Bose-Einstein Condensation in Dilute Gases. Cambridge University Press.  C. J. Pethick and H. Smith. 2001. Bose-Einstein Condensation in Dilute Gases. Cambridge University Press.","DOI":"10.1017\/CBO9780511755583"},{"volume-title":"Proceedings of the 4th Berkeley Symposium on Mathematical Statistics and Probability. 547--561","year":"1961","author":"R\u00e9nyi A.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"T. Richardson and R. Urbanke. 2008. Modern Coding Theory. Cambridge University Press.   T. Richardson and R. Urbanke. 2008. Modern Coding Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511791338"},{"key":"e_1_2_1_27_1","unstructured":"SAT-Competition. 2013. The International SAT Competitions Web Page. Retrieved from http:\/\/www. satcompetition.org\/.  SAT-Competition. 2013. The International SAT Competitions Web Page. Retrieved from http:\/\/www. satcompetition.org\/."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671972"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90389-W"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629498","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629498","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629498"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":29,"alternative-id":["10.1145\/2629498"],"URL":"https:\/\/doi.org\/10.1145\/2629498","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}