Related Experiment Videos
Percolation of unsatisfiability in finite dimensions
J M Schwarz1, A Alan Middleton
1Department of Physics, Syracuse University, Syracuse, New York 13244, USA.
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|November 5, 2004
Summary
This study explores two-dimensional Boolean formula optimization, finding no satisfiability transition but revealing a logical connectivity transition and solution time changes. Unique ground states are identified for this NP-hard problem.
Area of Science:
- Computational complexity theory
- Statistical physics
Background:
- Two-dimensional Boolean formulas present complex optimization challenges.
- Mean-field approaches often oversimplify the behavior of such systems.
Purpose of the Study:
- To investigate the optimization of two-dimensional Boolean formulas.
- To analyze phase transitions and solution time dynamics.
Main Methods:
- Percolation theory
- Rare region arguments
- Boundary effects analysis
Main Results:
- Absence of a satisfiability transition with varying constraint density.
- Identification of a logical connectivity transition.
- A transition in solution time observed in the disconnected phase.
- Unique thermodynamic ground state for the NP-hard optimization problem.
Conclusions:
- Local solutions can be combined to determine the global ground state.
- Findings offer insights into the computational study of disordered materials.