The generalized complexity of linear Boolean functions
- Authors
- Type
- Published Article
- Journal
- Discrete Mathematics and Applications
- Publisher
- De Gruyter
- Publication Date
- Feb 09, 2020
- Volume
- 30
- Issue
- 1
- Pages
- 39–44
- Identifiers
- DOI: 10.1515/dma-2020-0004
- Source
- De Gruyter
- Keywords
- License
- Yellow
Abstract
We study generalized (in terms of bases) complexity of implementation of linear Boolean functions by Boolean circuits in arbitrary functionally complete bases; the complexity of a circuit is defined as the number of gates. Let L*(n) be the minimal number of gates sufficient for implementation of an arbitrary linear Boolean function of n variables in an arbitrary functionally complete basis. We show that L*(0) = L*(1) = 3 and L*(n) = 7(n – 1) for any natural n ≥ 2.
