On the Perfectness of Minimal Regular Partitions of the Edge Set of the n-Dimensional Cube

被引：0

作者：

Rychkov K.L. ^{[1
]}

机构：

[1] Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk

来源：

Journal of Applied and Industrial Mathematics | 2019年 / 13卷 / 04期

关键词：

Boolean function; correct partition of the edge set of the n-dimensional cube; lower complexity bound; π-scheme;

D O I：

10.1134/S1990478919040148

中图分类号：

学科分类号：

摘要：

We prove that, for n equal to 3, 5, and a power of 2, every minimal partition of the edge set of the n-dimensional cube is perfect. As a consequence, we obtain some description of the classes of all minimal parallel-serial contact schemes (π-schemes) realizing the linear Boolean functions that depend essentially on n variables for the corresponding values of n. © 2019, Pleiades Publishing, Ltd.

引用

页码：717 / 739

页数：22

共 16 条

[1]

Khrapchenko V.M., Complexity of the Realization of a Linear Function in the Class of II-Circuits, Mat. Zametki, 9, 1, pp. 35-40, (1971)

[2]

Khrapchenko V.M., A Method of Determining Lower Bounds for the Complexity of II-Schemes, Mat. Zametki, 10, 1, pp. 83-92, (1971)

[3]

Khrapchenko V.M., A Simplified Proof of a Lower Complexity Estimate, Discrete Math, 25, 2, pp. 82-84, (2013)

[4]

Rychkov K.L., A Modification of Khrapchenko’s Method and Its Application to Estimation of Complexity of 7π-Schemes for Code Functions, Methods of Discrete Analysis in Theory of Graphs and Schemes, 42, pp. 91-98, (1985)

[5]

Razborov A., Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity, Combinatorica, 10, 1, pp. 81-93, (1990)

[6]

Karchmer M., Wigderson A., Monotone Circuits for Connectivity Require Super-Logarithmic Depth, SIAM J. Discrete Math, 3, 2, pp. 255-265, (1990)

[7]

Hastad J., The Shrinkage Exponent is 2, SIAM J. Comput, 27, 1, pp. 48-64, (1998)

[8]

Cherukhin D.Y., To the Question of a Logical Representation for the Parity Counter, Neform. Nauka No., 2, pp. 14-23, (2009)

[9]

Avgustinovich S.V., Vasil'ev Y.L., Rychkov K.L., The Computation Complexity in the Class of Formulas, Diskretn. Anal. Issled. Open, 19, 3, pp. 3-12, (2012)

[10]

Vasil'ev Y.L., Rychkov K.L., A Lower Bound on Formula Size of a Ternary Linear Function, Diskretn. Anal. Issled. Open, 20, 4, pp. 15-26, (2013)

← 1 2 →