Representations of normalized formulas

K. L. Rychkov

Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 4, pp. 77-103.

Résumé

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.

Détail

Keywords: Boolean function, normalized formula, representation of a formula, $\Pi$-scheme, lower bound for the complexity.
Mots-clés : minimal formula, $\Pi$-partition

Bibliographie

[1] V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of $\Pi$-circuits”, Math. Notes Acad. Sci. USSR, 9:1 (1971), 21–23 | MR

[2] S. V. Yablonskii, “Realization of a linear function in the class of $\pi$-circuits”, Dokl. Akad. Nauk SSSR, Nov. Ser., 94:5 (1954), 805–806 | MR

[3] K. L. Rychkov, “Lower bounds on the complexity of parallel-sequential switching circuits that realize linear Boolean functions”, Discrete Analysis and Operation Research, Math. Its Appl., 355, Kluwer Acad. Publ., Dordrecht, 1996, 217–234 | MR

[4] D. Yu. Cherukhin, “To the question of a logical representation for the parity counter”, Neform. Nauka, 2009, no. 2, 14–23

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

[6] K. L. Rychkov, “Complexity of the realization of a linear boolean function in the class of $\pi$-schemes”, J. Appl. Ind. Math., 12:3 (2018), 540–576 | DOI | MR

[7] K. L. Rychkov, “On minimal $\pi$-schemes for linear Boolean functions”, Sib. Adv. Math., 3:3 (1993), 172–185 | MR

[8] K. L. Rychkov, “Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating”, J. Appl. Ind. Math., 9:4 (2015), 580–587 | DOI | MR

[9] K. L. Rychkov, “On the perfectness of minimal regular partitions of the edge set of the n-dimensional cube”, J. Appl. Ind. Math., 13:4 (2019), 717–739 | DOI | MR | MR

[10] V. M. Khrapchenko, “A method of determining lower bounds for the complexity of $\Pi$-schemes”, Math. Notes Acad. Sci. USSR, 10:1 (1971), 474–479 | MR

[11] B. A. Subbotovskaya, “Realization of linear functions by formulas using $\vee$, $\wedge$, $^-$”, Dokl. Akad. Nauk, 136:3 (1961), 553–555 | MR

[12] V. M. Khrapchenko, “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174 | DOI | MR

[13] S. V. Avgustinovich, Yu. L. Vasil'ev, and K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Ind. Math., 6:4 (2012), 403–409 | DOI | MR | MR

[14] Yu. L. Vasil'ev and K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Ind. Math., 7:4 (2013), 490–499 | MR

[15] I. S. Sergeev, “Formula complexity of a linear function in a $k$-ary basis”, Math. Notes, 109:3 (2021), 445–458 | DOI | MR

[16] Razborov A., “Applications of matrix methods to the theory of lower bounds in computational complexity”, Combinatorica, 10:1 (1990), 81–93 | DOI | MR

[17] Karchmer M., Wigderson A., “Monotone circuits for connectivity require super-logarithmics depth”, SIAM J. Discrete Math., 3:2 (1990), 255–265 | DOI | MR

[18] Håstad J., “The shrinkage exponent is 2”, SIAM J. Comput., 27:1 (1998), 48–64 | DOI | MR