Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes

DOI10.1134/S1990478918030146zbMath1413.94077OpenAlexW2888000245MaRDI QIDQ4558295

K. L. Rychkov

Publication date: 21 November 2018

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478918030146

zbMATH Keywords

Boolean functionlower complexity bound\(\pi \)-scheme

Mathematics Subject Classification ID

Analytic circuit theory (94C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the formula complexity of a linear Boolean function
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• A New Rank Technique for Formula Size Lower Bounds
• The Shrinkage Exponent of de Morgan Formulas is 2
• Computation complexity of a ternary linear function
• A lower estimate for the computation complexity of a ternary linear function

This page was built for publication: Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes