Phys. Rev. E 70, 035103(R) (2004) [4 pages]Percolation of unsatisfiability in finite dimensions
The optimization of two-dimensional Boolean formulas is studied using percolation theory, rare region arguments, and boundary effects. In contrast with mean-field results, there is no satisfiability transition as the constraint density is varied, although there is a logical connectivity transition. In the disconnected phase, there is a transition in the solution time. The thermodynamic ground state for this NP-hard optimization problem is unique; local solutions can be adjoined to find the global ground state. These results have implications for the computational study of disordered materials. © 2004 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevE.70.035103
DOI:
10.1103/PhysRevE.70.035103
PACS:
05.70.Fh, 89.20.Ff, 64.60.Ak, 75.10.Nr
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.