Realization of linear functions by formulas in various bases
type: Item
instance of: scholarly article
title: Realization of linear functions by formulas in various bases
zbMATH Open document ID: 1028.94044
author: D. Yu. Cherukhin
published in: Moscow University Mathematics Bulletin
publication date: 2003-04-23T00:00:00Z
review text: The author studies the complexity of the realization of a linear Boolean function \(x_1\oplus\dots\oplus x_n\) by formulas in various bases. The author divides all the bases into three types: in the bases of the first type, the order of the complexity of realization of a linear function equals \(n^2\); in the bases of the second type, the order of complexity is not smaller than \(n^\beta\) and not larger than \(n^\gamma\), where \(1<\beta<\gamma<2\) (the constants \(\beta\) and \(\gamma\) are calculated with respect to the basis); and in the bases of the third type, the order of complexity equals \(n\).
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 1900006
zbMATH Keywords: realization of a linear function
zbMATH Keywords: various bases
zbMATH Keywords: Boolean function
zbMATH Keywords: complexity
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1900006