|
This article is cited in 5 scientific papers (total in 5 papers)
On the complexity of the problem of determining the number of solutions of systems of Boolean equations
S. P. Gorshkov
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).
Received: 09.09.1993
Citation:
S. P. Gorshkov, “On the complexity of the problem of determining the number of solutions of systems of Boolean equations”, Diskr. Mat., 8:1 (1996), 72–85; Discrete Math. Appl., 6:1 (1996), 77–92
Linking options:
https://www.mathnet.ru/eng/dm509https://doi.org/10.4213/dm509 https://www.mathnet.ru/eng/dm/v8/i1/p72
|
Statistics & downloads: |
Abstract page: | 676 | Full-text PDF : | 439 | First page: | 1 |
|