Bose-Einstein condensation in satisfiability problems
From MaRDI portal
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Quantum equilibrium statistical mechanics (general) (82B10)
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.
Recommendations
- Satisfiability by Maxwell-Boltzmann and Bose-Einstein statistical distributions
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
- Proof of the satisfiability conjecture for large \(k\)
- Statistical physics analysis of the backtrack resolution of random 3-SAT instances
- The SAT phase transition
Cited in
(2)
This page was built for publication: Bose-Einstein condensation in satisfiability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253621)
