zbMATH — the first resource for mathematics

Recognition complexity for Schaefer classes. (English. Russian original) Zbl 1026.94555
Mosc. Univ. Math. Bull. 51, No. 4, 6-9 (1996); translation from Vestn. Mosk. Univ., Ser. I 1996, No. 4, 7-12 (1996).
Let \(F = \{f_j(x_1,x_2,\dots,x_{k_j})\not\equiv 0\mid j\in J\}\) be a finite set of Boolean functions set in conjunctive normal form (CNF). The class of various systems of equations \[ \{f_{j_i}(x_{i1},x_{i2},\dots,x_{ik_{j_i}})\} = 1,\qquad i = \overline{1, m} \] is called the class of \(F\)-systems for any choice of the functions \(f_{j_i}\) from \(F\) with any finite number \(m\) of equations in each system and for any choice of unknown \(x_{ij}\) from the set \(X = \{x_1,x_2,\dots\}\). The problem of \(F\)-jointness is a problem of jointness recognizing an arbitrary system of equations from the class of \(F\)-systems. The set of functions \(F\) is called \(P\)-set, if there exist a polynomial algorithm solving the \(F\)-jointness problem and an \(NP\)-complete set, if the problem of \(F\)-jointness is \(NP\)-complete. The author proves that the problem of recognizing multiaffinity, bijunctiveness, weak-positiveness and weak-negativeness of a Boolean function given in CNF is \(NP\)-complete.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)