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 language | English (US) |
|---|---|
| Article number | 035103 |
| Pages (from-to) | 035103-1-035103-4 |
| Journal | Physical Review E - Statistical, Nonlinear, and Soft Matter Physics |
| Volume | 70 |
| Issue number | 3 2 |
| DOIs | |
| State | Published - Sep 2004 |
ASJC Scopus subject areas
- Statistical and Nonlinear Physics
- Statistics and Probability
- Condensed Matter Physics