|
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.
Received 20.IV.2015
Citation:
S. P. Gorshkov, “Functions from Schaefer classes having negations belonging to other Schaefer classes”, Mat. Vopr. Kriptogr., 6:4 (2015), 23–48
Linking options:
https://www.mathnet.ru/eng/mvk166https://doi.org/10.4213/mvk166 https://www.mathnet.ru/eng/mvk/v6/i4/p23
|
Statistics & downloads: |
Abstract page: | 363 | Full-text PDF : | 256 | References: | 60 | First page: | 17 |
|