Title

Percolation of Satisfiability in Finite Dimensions

Author(s)/Creator(s)

Alan Middleton, Syracuse UniversityFollow
J. M. Schwarz, Syracuse University

Document Type

Article

Date

9-10-2003

Language

English

Disciplines

Physics

Description/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.

Additional Information

4 pages, 4 figs More information at http://arxiv.org/abs/cond-mat/0309240

Recommended Citation

Middleton, Alan and Schwarz, J. M., "Percolation of Satisfiability in Finite Dimensions" (2003). Physics - All Scholarship. 189.
https://surface.syr.edu/phy/189

Source

Harvested from Arxiv.org

Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 License.