# 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.

##### MSC:
 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
##### Keywords:
Schaefer classes; recognition