Percolation of satisfiability in finite dimensions
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
The satisfiability and optimization of finite-dimensional Boolean formulas are studied using percolation theory, rare region arguments, and boundary effects. In contrast with mean-field results, there is no satisfiability transition, though there is a logical connectivity transition. In part of the disconnected phase, rare regions lead to a divergent running time for optimization algorithms. The thermodynamic ground state for the NP-hard two-dimensional maximum-satisfiability problem is typically unique. These results have implications for the computational study of disordered materials.
4 pages, 4 figs
4 pages, 4 figs