Geodesic
Functions from Schaefer classes having negations belonging to other Schaefer classes
Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 4, pp. 23-48 
S. P. Gorshkov. Functions from Schaefer classes having negations belonging to other Schaefer classes. Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 4, pp. 23-48. http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a1/
@article{MVK_2015_6_4_a1,
     author = {S. P. Gorshkov},
     title = {Functions from {Schaefer} classes having negations belonging to other {Schaefer} classes},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {23--48},
     year = {2015},
     volume = {6},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a1/}
}
TY  - JOUR
AU  - S. P. Gorshkov
TI  - Functions from Schaefer classes having negations belonging to other Schaefer classes
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 23
EP  - 48
VL  - 6
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a1/
LA  - ru
ID  - MVK_2015_6_4_a1
ER  - 
%0 Journal Article
%A S. P. Gorshkov
%T Functions from Schaefer classes having negations belonging to other Schaefer classes
%J Matematičeskie voprosy kriptografii
%D 2015
%P 23-48
%V 6
%N 4
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a1/
%G ru
%F MVK_2015_6_4_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

Multiaffine, bijunctive ($2$-CNF), weakly positive and weakly negative (Horn's) Boolean functions generates polynomially solvable systems of equations. These sets of Boolean functions are called the Schaefer classes. We describe sets of Boolean functions $f$ from any Schaefer class such that $f$ belongs to another Schaefer class. The results obtained may be applied to the solution of systems of Boolean equations.

[1] Schaefer T., “Complexity of satisfiability problems”, Proc. 10 Annual ACM Symp. on Theory of Computing Machinery, 1978, 216–226 | MR | Zbl

[2] Gizunov S. A., Nosov V. A., “O klassifikatsii vsekh bulevykh funktsii chetyrekh peremennykh po klassam Shefera”, Obozr. prikl. i promyshl. matem., 2:3 (1995), 440–467

[3] Gorshkov S. P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozr. prikl. i promyshl. matem., 2:3 (1995), 325–398