Percolation of unsatisfiability in finite dimensions

Research output: Contribution to journalArticle

2 Citations (Scopus)

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
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume70
Issue number3 2
DOIs
StatePublished - Sep 2004

Fingerprint

Percolation Theory
Binary
optimization
Optimization

ASJC Scopus subject areas

  • Physics and Astronomy(all)
  • Condensed Matter Physics
  • Statistical and Nonlinear Physics
  • Mathematical Physics

Cite this

@article{93878cb87fac459b845b8fa8d794de17,
title = "Percolation of unsatisfiability in finite dimensions",
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.",
author = "Schwarz, {Jennifer M} and Middleton, {Arthur Alan}",
year = "2004",
month = "9",
doi = "10.1103/PhysRevE.70.035103",
language = "English (US)",
volume = "70",
journal = "Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics",
issn = "1063-651X",
publisher = "American Physical Society",
number = "3 2",

}

TY - JOUR

T1 - Percolation of unsatisfiability in finite dimensions

AU - Schwarz, Jennifer M

AU - Middleton, Arthur Alan

PY - 2004/9

Y1 - 2004/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=42749107443&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=42749107443&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.70.035103

DO - 10.1103/PhysRevE.70.035103

M3 - Article

C2 - 15524567

AN - SCOPUS:42749107443

VL - 70

JO - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

JF - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

SN - 1063-651X

IS - 3 2

M1 - 035103

ER -