Realization of linear functions by formulas in various bases
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\).
- On the complexity of realization of the linear function by formulas over finite Boolean bases
- The generalized complexity of linear Boolean functions
- Formula complexity of a linear function in a \(k\)-ary basis
- Complexity of realization of a linear Boolean function in Sheffer's basis
- Realization of Boolean functions by formulas in continuous bases containing a continuum of constants
- Realization of Boolean functions by formulas in continuous bases containing a continuum of constants
- Formula complexity of a linear function in a \(k\)-ary basis
- The generalized complexity of linear Boolean functions
- Arithmetic complexity of certain linear transformations
- Complexity of implementation of Boolean functions by real-valued formulas
- scientific article; zbMATH DE number 4027365 (Why is no real title available?)
- On the premaximal Boolean bases
- On the complexity of realization of the linear function by formulas over finite Boolean bases
- scientific article; zbMATH DE number 3328172 (Why is no real title available?)
- Lower bounds on the formula complexity of a linear Boolean function
This page was built for publication: Realization of linear functions by formulas in various bases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1866895)
