On the complexity of the problem of determining the number of solutions of systems of Boolean equations

S. P. Gorshkov

Diskretnaya Matematika, Tome 8 (1996) no. 1, pp. 72-85

Résumé

We consider classes of systems of Boolean equations of the form \[ f_{s_i}(x_{s_{i1}},\ldots,x_{s_{ik_{i}}}) = 1,\qquad i = 1,\ldots,m, \] where $m \in \{ 1,2,\ldots\}$, $x_{s_{ij}} \in \{ x_{1},x_{2},\ldots\}$, $j = 1,\ldots,k_{i}$, $i = 1,\ldots,m$, the functions ${f}_{s_{i}}$ are taken from a set of Boolean functions $F = \{ f_{j}(x_{1},\ldots,x_{k_j}\mid j\in J \}$. The problem of finding the number of solutions of a system of equations from this class is denoted by $\enu([F]_{\NC})$, and the set of all Boolean functions, which can be represented as a conjunction of affine functions is denoted by $A$. It is proved that if $F \subseteq A$, then the problem $\enu([F]_{\NC})$ is polynomial, if $F \mathrel{\scriptstyle\nsubseteq} A$, then the problem $\enu([F]_{\NC})$ is $\NP$-complete (intractable).