Abstract:
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).
Fulltext:
PDF file (1423 kB)