Affordable Access

Access to the full text

The generalized complexity of linear Boolean functions

Authors
  • Redkin, Nikolay P.1
  • 1 Lomonosov Moscow State University, Russia , (Russia)
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.

Report this publication

Statistics

Seen <100 times