Research Repository

Bose–Einstein condensation in satisfiability problems

Angione, Claudio and Occhipinti, Annalisa and Stracquadanio, Giovanni and Nicosia, Giuseppe (2013) 'Bose–Einstein condensation in satisfiability problems.' European Journal of Operational Research, 227 (1). pp. 44-54. ISSN 0377-2217

Full text not available from this repository.

Abstract

This paper is concerned with the complex behavior arising in satisfiability problems. We present a new statistical physics-based characterization of the satisfiability problem. Specifically, we design an algorithm that is able to produce graphs starting from a k-SAT instance, in order to analyze them and show whether a Bose-Einstein condensation occurs. We observe that, analogously to complex networks, the networks of k-SAT instances follow Bose statistics and can undergo Bose-Einstein condensation. In particular, k-SAT instances move from a fit-get-rich network to a winner-takes-all network as the ratio of clauses to variables decreases, and the phase transition of k-SAT approximates the critical temperature for the Bose-Einstein condensation. Finally, we employ the fitness-based classification to enhance SAT solvers (e.g.; ChainSAT) and obtain the consistently highest performing SAT solver for CNF formulas, and therefore a new class of efficient hardware and software verification tools. © 2012 Elsevier B.V. All rights reserved.

Item Type: Article
Uncontrolled Keywords: k-SAT; Complex networks; Bose-Einstein condensation; Phase transition; Performance
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 07 Feb 2017 12:37
Last Modified: 06 Jan 2022 14:43
URI: http://repository.essex.ac.uk/id/eprint/18699

Actions (login required)

View Item View Item