On the complexity of realization of the linear function by formulas over finite Boolean bases

DOI10.1515/DMA.2000.10.2.147MaRDI QIDQ4522865zbMATH OpenOpenAlexFDO

Authors D. Yu. Cherukhin

Publication date 26 July 2001

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.2000.10.2.147

zbMATH Keywords

basesBoolean functionscomplexity of realizationlower bound

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Logical aspects of Boolean algebras (03G05) Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Realization of linear functions by formulas in various bases
• The generalized complexity of linear Boolean functions
• On the complexity of circuit realization of Boolean functions in an infinite basis
• On an infinite sequence of improving Boolean bases
• On the comparison of Boolean bases

Cited in

(27)

• Realization of systems of Boolean functions by linear arithmetic polynomials with masking
• On the complexity of realizing the powers of a Boolean (n,n)-function
• Realization of Boolean formulas by uniform multiplexor and majority cascades
• Realization of linear functions by formulas in various bases
• Realization of Boolean functions by formulas in continuous bases containing a continuum of constants
• Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3
• Formula complexity of a linear function in a \(k\)-ary basis
• The generalized complexity of linear Boolean functions
• Exact value of the nonmonotone complexity of Boolean functions
• Complexity of linear and majority functions in the basis of antichain functions
• On sets of linear forms of maximal complexity
• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• On minimal circuits for linear functions over some bases
• On the complexity of realization of Boolean functions by formulas
• On the complexity of circuit realization of Boolean functions in an infinite basis
• scientific article; zbMATH DE number 5005220 (Why is no real title available?)
• Lower estimates of circuit complexity in the basis of antichain functions
• Complexity of realization of a linear Boolean function in Sheffer's basis
• Complexity of implementation of Boolean functions by real-valued formulas
• scientific article; zbMATH DE number 3970686 (Why is no real title available?)
• scientific article; zbMATH DE number 4027365 (Why is no real title available?)
• scientific article; zbMATH DE number 4031581 (Why is no real title available?)
• scientific article; zbMATH DE number 1746570 (Why is no real title available?)
• On the complexity of joint realization of Boolean functions regular systems in the DNF basis
• On an infinite sequence of improving Boolean bases
• Which bases admit non-trivial shrinkage of formulae?
• Lower bounds on the formula complexity of a linear Boolean function

This page was built for publication: On the complexity of realization of the linear function by formulas over finite Boolean bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4522865)