Percolation of unsatisfiability in finite dimensions

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The two-dimensional Boolean formula optimization was studied using percolation theory, rare region arguments and binary effects. The Boolean formulas were decomposed into components that contain logical contradiction. It was observed that there was non satisfiability transition as the constraint density was varied. A percolation transition in the logical structure of the formula was observed as the clause density was increased.

Original languageEnglish (US)
Article number035103
Pages (from-to)035103-1-035103-4
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Issue number3 2
StatePublished - Sep 2004

ASJC Scopus subject areas

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


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

Cite this