The generalized complexity of linear Boolean functions

被引：0

作者：

Redkin, Nikolay P. ^{[1
]}

机构：

[1] Lomonosov Moscow State Univ, Moscow, Russia

来源：

DISCRETE MATHEMATICS AND APPLICATIONS | 2020年 / 30卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

Boolean function; Boolean circuit; complexity of a Boolean function; Shannon function;

D O I：

10.1515/dma-2020-0004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：39 / 44

页数：6

共 12 条

[1] The Minimal Circuits for Linear Boolean Functions [J].

Kombarov, Yu. A. .

MOSCOW UNIVERSITY MATHEMATICS BULLETIN, 2011, 66 (06) :260-263

[2] On minimal circuits for linear functions over some bases [J].

Kombarov, Yu. A. .

DISCRETE MATHEMATICS AND APPLICATIONS, 2013, 23 (01) :39-51

[3]

Kombarov Yu. A., MOSCOW U MATH B, V68, P114

[4]

Kombarov Yu. A., 2012, J APPL IND MATH, V19, P39

[5]

[Комбаров Юрий Анатольевич Kombarov Yurii Anatol’evich], 2013, [Дискретный анализ и исследование операций, Diskretnyi analiz i issledovanie operatsii], V20, P65

[6]

Lupanov O. B., 1984, ASYMPTOTIC COMPLEXIT

[7]

Red'kin N. P., 1970, Problemy Kibernetiki, P83

[8]

Redkin N. P., 1989, MAT VOPR KIBERN, V2, P198

[9]

Redkin N. P., 1971, KIBERNETIKA, P31

[10] A generalization of Shannon function [J].

Redkin, Nikolay P. .

DISCRETE MATHEMATICS AND APPLICATIONS, 2018, 28 (05) :309-318

← 1 2 →