Volume 25, No 3, 2018, P. 36-94

UDC 519.714
K. L. Rychkov
Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes

Abstract:
Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of $\pi$-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.
Bibliogr. 18.

Keywords: Boolean function, $\pi$-scheme, lower complexity bound.

DOI: 10.17377/daio.2018.25.589

Konstantin L. Rychkov ¹
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rychkov@math.nsc.ru

Received 18 September 2017
Revised 10 May 2018

References

[1] S. V. Avgustinovich, Yu. L. Vasil’ev, and K. L. Rychkov, The computation complexity in the class of formulas, Diskretn. Anal. Issled. Oper., 19, No. 3, 3–12, 2012 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 4, 403–409, 2012.

[2] Yu. L. Vasil’ev and K. L. Rychkov, A lower bound on formula size of a ternary linear function, Diskretn. Anal. Issled. Oper., 20, No. 4, 15–26, 2013 [Russian]. Translated in J. Appl. Ind. Math., 7, No. 4, 490–499, 2013.

[3] K. L. Rychkov, A modification of Khrapchenko’s method and its application to estimation of complexity of $\pi$-schemes for code functions, in Methods of Discrete Analysis in Theory of Graphs and Schemes, Vol. 42, pp. 91–98, Izd. Inst. Mat., Novosibirsk, 1985 [Russian].

[4] K. L. Rychkov, On the lower bounds for the complexity of serial-parallel contact circuits realizing linear Boolean functions, Sib. Zh. Issled. Oper., 1, No. 4, 33–52, 1994 [Russian]. Translated in Discrete Analysis and Operations Research, pp. 217–234, Kluwer Acad. Publ., Dordrecht, 1996 (Math. Its Appl., Vol. 355).

[5] K. L. Rychkov, Lower bounds on the formula complexity of a linear Boolean function, Sib. Elektron. Mat. Izv., 11, 165–184, 2014 [Russian].

[6] K. L. Rychkov, Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating, Diskretn. Anal. Issled. Oper., 22, No. 5, 71–85, 2015 [Russian].

[7] B. A. Subbotovskaya, Realization of linear functions by formulas using $\lor, \And, -$, Dokl. Akad. Nauk SSSR, 136, No. 3, 553–555, 1961 [Russian]. Translated in Sov. Math., Dokl., 2, 110–112, 1961.

[8] V. M. Khrapchenko, Complexity of the realization of a linear function in the class of $\Pi$-circuits, Mat. Zametki, 9, No. 1, 35–40, 1971 [Russian]. Translated in Math. Notes Acad. Sci. USSR, 9, No. 1, 21–23, 1971.

[9] V. M. Khrapchenko, A method of determining lower bounds for the complexity of $\Pi$-schemes, Mat. Zametki, 10, No. 1, 83–92, 1971 [Russian]. Translated in Math. Notes Acad. Sci. USSR, 10, No. 1, 474–479, 1971.

[10] D. Yu. Cherukhin, To the question of a logical representation for the parity counter, Neform. Nauka, No. 2, 14–23, 2009 [Russian].

[11] S. V. Yablonskii, Realization of a linear function in the class of $\Pi$-circuits, Dokl. Akad. Nauk SSSR, Nov. Ser., 94, No. 5, 805–806, 1954 [Russian].

[12] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

[13] J. Håstad, The shrinkage exponent of de Morgan formulas is 2, SIAM J. Comput., 27, No. 1, 48–64, 1998.

[14] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math., 3, No. 2, 255–265, 1990.

[15] T. Lee, A new rank technique for formula size lower bounds, in Proc. 24th Annu. Symp. Theor. Asp. Comput. Sci., Aachen, Germany, Feb. 22–24, 2007, pp. 145–156, Springer, Heidelberg, 2007 (Lect. Notes Comput. Sci., Vol. 4393).

[16] A. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica, 10, No. 1, 81–93, 1990.

[17] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, No. 1, 436–452, 1941 [Hungarian].

[18] I. Wegener, The Complexity of Boolean Functions, Wiley, Chichester, UK, 1987.