Percolation of satisfiability in finite dimensions
arXiv:cond-mat/0309240 · doi:10.1103/PhysRevE.70.035103
Abstract
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
References in corpus (8)
- The Scaling Window of the 2-SAT Transition
- Ordering and Broken Symmetry in Short-Ranged Spin Glasses
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Numerical investigation of the thermodynamic limit for ground states in models with quenched disorder
- Trivial Ground State Structure in the Two-Dimensional Ising Spin Glass
- Statistical mechanics of the vertex-cover problem
- Critical properties of loop percolation models with optimization constraints