Email this article Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes
- Authors: Rychkov K.L.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Issue: Vol 12, No 3 (2018)
- Pages: 540-576
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213100
- DOI: https://doi.org/10.1134/S1990478918030146
- ID: 213100
Cite item
Open Access
Access granted
Subscription Access
Abstract
Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.
Keywords
About the authors
K. L. Rychkov
Sobolev Institute of Mathematics
Author for correspondence.
Email: rychkov@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090
