Percolation of unsatisfiability in finite dimensions

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)4
Number of pages1
JournalPhysical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Volume70
Issue number3
DOIs
StatePublished - 2004

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics

Fingerprint

Dive into the research topics of 'Percolation of unsatisfiability in finite dimensions'. Together they form a unique fingerprint.

Cite this