Percolation of satisfiability in finite dimensions
| dc.creator | Schwarz, J. M. | |
| dc.creator | Middleton, A. Alan | |
| dc.date | 2003-09-10 | |
| dc.date.accessioned | 2026-07-07T02:53:22Z | |
| dc.date.available | 2026-07-07T02:53:22Z | |
| dc.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. | |
| dc.description | 4 pages, 4 figs | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0309240 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0309240 | |
| dc.identifier | Physical Review E 70, 035103 (R) (2004) [4 pages] | |
| dc.identifier | doi:10.1103/PhysRevE.70.035103 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/22191 | |
| dc.subject | Condensed Matter | |
| dc.title | Percolation of satisfiability in finite dimensions | |
| dc.type | text |