کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476784 1446056 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bose–Einstein condensation in satisfiability problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Bose–Einstein condensation in satisfiability problems
چکیده انگلیسی

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.


► New BEC-driven algorithm to translate a k-SAT instance into a network.
► The network presents a BE phase transition as a function of α = clauses/variables.
► The k-SAT phase transition approximates the critical temperature for the BEC.
► We obtain the highest performing SAT solver by using a fitness-based classification.
► We connect k-SAT problem, complex networks and condensation phase transition.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 227, Issue 1, 16 May 2013, Pages 44–54
نویسندگان
, , , ,