Geodesic
Investigation of some subclasses of multiaffine, bijunctive, weakly positive and weakly negative Boolean functions
Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 4, pp. 51-66 
S. P. Gorshkov. Investigation of some subclasses of multiaffine, bijunctive, weakly positive and weakly negative Boolean functions. Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 4, pp. 51-66. http://geodesic.mathdoc.fr/item/MVK_2016_7_4_a3/
@article{MVK_2016_7_4_a3,
     author = {S. P. Gorshkov},
     title = {Investigation of some subclasses of multiaffine, bijunctive, weakly positive and weakly negative {Boolean} functions},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {51--66},
     year = {2016},
     volume = {7},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2016_7_4_a3/}
}
TY  - JOUR
AU  - S. P. Gorshkov
TI  - Investigation of some subclasses of multiaffine, bijunctive, weakly positive and weakly negative Boolean functions
JO  - Matematičeskie voprosy kriptografii
PY  - 2016
SP  - 51
EP  - 66
VL  - 7
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MVK_2016_7_4_a3/
LA  - ru
ID  - MVK_2016_7_4_a3
ER  - 
%0 Journal Article
%A S. P. Gorshkov
%T Investigation of some subclasses of multiaffine, bijunctive, weakly positive and weakly negative Boolean functions
%J Matematičeskie voprosy kriptografii
%D 2016
%P 51-66
%V 7
%N 4
%U http://geodesic.mathdoc.fr/item/MVK_2016_7_4_a3/
%G ru
%F MVK_2016_7_4_a3

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

Sets of multiaffine (denoted by $A$), bijunctive ($2$-CNF, $Bi$), weakly positive (or anti-Horn, $WP$) and weakly negative (or Horn, $WN$) Boolean functions generate classes of polynomially solvable systems of equations. We investigate functional classes $A\cap B$, $Bi\cap B$, where $B$ is the set of bent functions. Sets of possible values of algebraic nonlinearity degree of functions from $A$, $Bi$, $WP$, $WN$ are described. Problems of construction of functions from classes $WP$, $WN$ by means of functions of smaller number of variables are considered.

[1] Schaefer T., “Complexity of satisfiability problems”, Proc. 10 Annu. ACM Symp. Theory Comput. Machin., 1978, 216–226 | MR | Zbl

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

[3] Glukhov M. M., Shishkov A. B., Matematicheskaya logika. Diskretnye funktsii. Teoriya algoritmov, Lan, SPb., 2012

[4] Tarasov A. V., “O svoistvakh funktsii, predstavlennykh v vide 2-KNF”, Diskretnaya matematika, 13:4 (2001), 99–115 | DOI

[5] Gorshkov S. P., “O nekotorykh svoistvakh slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Prikladnaya diskretnaya matematika, 20, iyun (2013), 5–13

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