Percolation of unsatisfiability in finite dimensions

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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
Volume70
Issue number3 2
DOIs
StatePublished - Sep 1 2004

    Fingerprint

ASJC Scopus subject areas

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

Cite this