On the complexity of weakly positive and weakly negative boolean functions reducing

S. P. Gorshkov

Prikladnaâ diskretnaâ matematika, no. 1 (2008), pp. 7-9.

Résumé

Boolean function $f(x_1,\dots,x_k)$ is called weakly positive (weakly negative) if $f$ may be represented by CNF such as $f\equiv\bigwedge\limits_{i=1}^t(x_{s_{i1}}^{\alpha_i}\lor x_{s_{i2}}\lor\dots\lor x_{s_{ik_i}})$, where $\alpha_i\in\{0,1\}$, $i=1,\dots,t$, (respectively by CNF such as $f\equiv\bigwedge\limits_{i=1}^t(\overline x_{s_{i1}}^{\alpha_i}\lor\overline x_{s_{i2}}\lor\dots\lor\overline x_{s_{ik_i}})$, where $\alpha_i\in\{0,1\}$, $i=1,\dots,t$). These formulas are called reduced representations of weakly positive and weakly negative functions accordingly. The complexity of reducing the weakly positive and weakly negative functions represented by perfect CNF or algebraic normal form is evaluated in this paper.