Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes
- Autores: Rychkov K.1
-
Afiliações:
- Sobolev Institute of Mathematics
- Edição: Volume 12, Nº 3 (2018)
- Páginas: 540-576
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213100
- DOI: https://doi.org/10.1134/S1990478918030146
- ID: 213100
Citar
Resumo
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.
Palavras-chave
Sobre autores
K. Rychkov
Sobolev Institute of Mathematics
Autor responsável pela correspondência
Email: rychkov@math.nsc.ru
Rússia, pr. Akad. Koptyuga 4, Novosibirsk, 630090