Volume 22, No 5, 2015, P. 71-85
UDC 519.714
Rychkov K. L.
Sufficient conditions for the minimal π-schemes for linear Boolean functions to be locally non-repeating
Abstract:
We formulate sufficient conditions for the minimal π-schemes for linear Boolean functions to be locally non-repeating. The validity of these conditions gives a description of the classes of all minimal π-schemes for linear Boolean functions which depend essentially on n variables.
Ill. 2, bibliogr. 12.
Keywords: formula size, π-scheme, lower bound on the complexity.
DOI: 10.17377/daio.2015.22.481
Konstantin L. Rychkov 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rychkov@math.nsc.ru
Received 16 March 2015
Revised 23 July 2015
References
[1] K. L. Rychkov, A modification of Khrapchenko’s method and its application to estimation of complexity of π-schemes for code functions, in Metody diskretnogo analiza v teorii grafov i skhem (Methods of Discrete Analysis in Theory of Graphs and Schemes), Vol. 42, pp. 91–98, Izd. Inst. Mat., Novosibirsk, 1985.
[2] K. L. Rychkov, On minimal π-schemes for linear Boolean functions, in Metody diskretnogo analiza v sinteze realizatsii bulevykh funktsii (Methods of Discrete Analysis in Synthesis of Schemes for Boolean Functions), Vol. 51, pp. 84–104, Izd. Inst. Mat., Novosibirsk, 1991. Translated in Sib. Adv. Math., 3, No. 3, 172–185, 1993.
[3] 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. Translated in A. D. Korshunov, ed., Discrete Analysis and Operation Research, pp. 217–234, Kluwer Acad. Publ., Dordrecht, 1996 (Math. Its Appl., Vol. 355).
[4] K. L. Rychkov, Lower bounds on the formula complexity of a linear Boolean function, Sib. Elektron. Mat. Izv., 11, 165–184, 2014.
[5] V. M. Khrapchenko, Complexity of the realization of a linear function in the class of Ï-circuits, Mat. Zametki, 9, No. 1, 35–40, 1971. Translated in Math. Notes Acad. Sci. USSR, 9, No. 1, 21–23, 1971.
[6] V. M. Khrapchenko, A method of determining lower bounds for the complexity of Ï-schemes, Mat. Zametki, 10, No. 1, 83–92, 1971. Translated in Math. Notes Acad. Sci. USSR, 10, No. 1, 474–479, 1971.
[7] D. Yu. Cherukhin, To the question of a logical representation for the parity counter, Neform. Nauka, No. 2, 14–23, 2009.
[8] S. V. Yablonskii, Realization of a linear function in the class of π-circuits, Dokl. Akad. Nauk SSSR, Nov. Ser., 94, No. 5, 805–806, 1954.
[9] J. Håstad, The shrinkage exponent of de Morgan formulas is 2, SIAM J. Comput., 27, No. 1, 48–64, 1998.
[10] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math., 3, No. 2, 255–265, 1990.
[11] A. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica, 10, No. 1, 81–93, 1990.
[12] I. Wegener, The Complexity of Boolean Functions, Wiley, Chichester, UK, 1987.
