RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2015 Volume 6, Issue 4, Pages 23–48 (Mi mvk166)

Functions from Schaefer classes having negations belonging to other Schaefer classes

S. P. Gorshkov

Academy of Cryptography of the Russian Federation, Moscow

Abstract: 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.

Key words: multiaffine Boolean functions, $2$-CNF, Horn's Boolean functions, systems of Boolean equations.

UDC: 519.571

Received 20.IV.2015

DOI: 10.4213/mvk166



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025