Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 4, 2022, P. 77-103
UDC 519.714
K. L. Rychkov
Representations of normalized formulas
Abstract:
A class of objects called $\Pi$-partitions is defined. These objects, in a certain well-defined sense, are the equivalents of formulas in a basis consisting of disjunction, conjunction and negation, in which negations are possible only over variables (normalized formulas). $\Pi$-partitions are seen as representations of formulas, just as equivalents and graphical representations of the same formulas can be considered $\Pi$-schemes. Some theory of such representations has been developed which is essentially a mathematical apparatus focused on describing a class of minimal normalized formulas implementing linear Boolean functions.
Bibliogr. 18.
Keywords: Boolean function, normalized formula, minimal formula, representation of a formula, $\Pi$-scheme, $\Pi$-partition, lower bound for the complexity.
DOI: 10.33048/daio.2022.29.751
Konstantin L. Rychkov 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rychkov@math.nsc.ru
Received August 26, 2022
Revised August 26, 2022
Accepted August 31, 2022
References
[1] V. M. Khrapchenko, Complexity of the realization of a linear function in the class of $\Pi$-circuits, Mat. Zametki 9 (1), 35–40 (1971) [Russian] [Math. Notes Acad. Sci. USSR 9 (1), 21–23 (1971)].[2] S. V. Yablonskii, Realization of a linear function in the class of $\Pi$-circuits, Dokl. Akad. Nauk SSSR, Nov. Ser. 94 (5), 805–806 (1954).
[3] K. L. Rychkov, Lower bounds on the complexity of parallel-sequential switching circuits that realize linear Boolean functions, Sib. Zh. Issled. Oper. 1 (4), 33–52 (1994) [Russian] [Discrete Analysis and Operation Research (Kluwer Acad. Publ., Dordrecht, 1996), pp. 217–234 (Math. Its Appl., Vol. 355)].
[4] D. Yu. Cherukhin, To the question of a logical representation for the parity counter, Neform. Nauka, No. 2, 14–23 (2009).
[5] K. L. Rychkov, Lower bounds on the formula complexity of a linear Boolean function, Sib. Elektron. Mat. Izv. 11, 165–184 (2014).
[6] K. L. Rychkov, Complexity of the realization of a linear boolean function in the class of $\pi$-schemes, Diskretn. Anal. Issled. Oper. 25 (3), 36–94 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 540–576 (2018)].
[7] K. L. Rychkov, On minimal $\pi$-schemes for linear Boolean functions, Methods of Discrete Analysis in Synthesis of Schemes for Boolean Functions, Vol. 51 (Izd. Inst. Mat., Novosibirsk, 1991), pp. 84–104 [Russian] [Sib. Adv. Math. 3 (3), 172–185 (1993)].
[8] K. L. Rychkov, Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating, Diskretn. Anal. Issled. Oper. 22 (5), 71–85 (2015) [Russian] [J. Appl. Ind. Math. 9 (4), 580–587 (2015)].
[9] K. L. Rychkov, On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube, Diskretn. Anal. Issled. Oper. 26 (4), 74–107 (2019) [Russian] [J. Appl. Ind. Math. 13 (4), 717–739 (2019)].
[10] V. M. Khrapchenko, A method of determining lower bounds for the complexity of $\Pi$-schemes, Mat. Zametki 10 (1), 83–92 (1971) [Russian] [Math. Notes Acad. Sci. USSR 10 (1), 474–479 (1971)].
[11] B. A. Subbotovskaya, Realization of linear functions by formulas using $\lor, $\land, -$, Dokl. Akad. Nauk 136 (3), 553–555 (1961).
[12] V. M. Khrapchenko, A simplified proof of a lower complexity estimate, Discrete Math. 25 (2), 82–84 (2013) [Russian] [Discrete Math. Appl. 23 (2), 171–174 (2013)].
[13] S. V. Avgustinovich, Yu. L. Vasil’ev, and K. L. Rychkov, The computation complexity in the class of formulas, Diskretn. Anal. Issled. Oper. 19 (3), 3–12 (2012) [Russian] [J. Appl. Ind. Math. 6 (4), 403–409 (2012)].
[14] Yu. L. Vasil’ev and K. L. Rychkov, A lower bound on formula size of a ternary linear function, Diskretn. Anal. Issled. Oper. 20 (4), 15–26 (2013) [Russian] [J. Appl. Ind. Math. 7 (4), 490–499 (2013)].
[15] I. S. Sergeev, Formula complexity of a linear function in a $k$-ary basis, Mat. Zametki 109 (3), 419–435 (2021) [Russian] [Math. Notes 109 (3), 445–458 (2021)].
[16] A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1), 81–93 (1990).
[17] M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math. 3 (2), 255–265 (1990).
[18] J. Håstad, The shrinkage exponent is 2, SIAM J. Comput. 27 (1), 48–64 (1998).
