List of issues > Series «Mathematics». 2026. Vol 57
On the Complexity of the Linear Boolean Function in Some
Classes of Generalized Contact Circuits
Author(s)
Evgenii K. Mikhalev, Sergei A. Lozhkin
Lomonosov Moscow State University, Moscow, Russian Federation
Abstract
The paper considers a class of generalized contact circuits of rank 𝑟, in which
contacts are controlled only by linear logic algebra functions that depend on no more
than 𝑟 Boolean variables, as well as two of its subclasses with additional restrictions
on the location of contacts. The complexity of the implementation of the linear boolean
function 𝑙𝑛 from 𝑛 boolean variables in the specified classes of generalized contact circuits
is investigated. For a fixed 𝑟 and 𝑛 = 1, 2, ..., upper and lower estimates of the complexity
of the implementation of 𝑙𝑛 in each of the two above-mentioned subclasses of the class of
generalized contact circuits are obtained. Moreover, in the first subclass, the estimates
obtained are asymptotically equal to 4 𝑛𝑟
and differ from each other by the amount of𝑂(√︀𝑛𝑟), and in the second subclass they give its exact value of the form 4⌈𝑛𝑟⌉ − 4.
About the Authors
Evgenii K. Mikhalev, Student, Lomonosov Moscow State University, Moscow, 119991, Russian Federation, genya.mikhalev@gmail.com
Sergei A. Lozhkin, Dr. Sci. (Phys.-Math.), Prof., Lomonosov Moscow State University, Moscow, 119991, Russian Federation, lozhkin@cs.msu.ru
For citation
Mikhalev E. K., Lozhkin S. A. On the Complexity of the Linear Boolean
Function in Some Classes of Generalized Contact Circuits. The Bulletin of Irkutsk State
University. Series Mathematics, 2026, vol. 57, pp. 128–142. (in Russian)
https://doi.org/10.26516/1997-7670.2026.57.128
Keywords
generalized contact circuit, linear boolean function, complexity
UDC
519.71
MSC
06E30, 05C99
DOI
https://doi.org/10.26516/1997-7670.2026.57.128
References
- Voronenko A.A. On one property of linear boolean functions. Bulletin of the Moscow University. Computational Mathematics and Cybernetics, 2021, no. 2, pp. 43–44.
- Lozhkin S. A., Koshkin N. A. On the complexity of the implementation of some systems of boolean functions by contact and generalized contact circuits. Lecture Notes in Computer Science, 1987, vol. 28, pp. 293–296.
- Lozhkin S. A., Koshkin N. A. On the complexity of the implementation of some systems of functions of logic algebra by contact multipolytes. Rep. USSR Academy of Sciences, 1988, vol. 298, no. 4, pp. 807–81.
- Lozhkin S. A. Lectures on the basics of cybernetics. Moscow, MSU, 2004. 253 p.
- Lozhkin S. A., Mikhalev E. K. On the complexity of the linear boolean function in some classes of generalized contact circuits. Problems of theoretical cybernetics: proceedings of the XX International Scientific Conference (Moscow, December 5–8, 2024) Moscow: MAKS Press, 2025, pp. 82–84 https://doi.org/10.29003/m4678.978-5-317-07402-9
- Podolskaya O. V. Complexity of linear and majority functions in the basis of antichain functions. Moscow University Mathematics Bulletin, 2016, vol. 71, pp. 82–83. https://doi.org/10.3103/S002713221602008X
- Romanov D. S., Romanova E. Yu. On single detecting test sets for circuits of switching type. University proceedings. Volga region. Physical and mathematical sciences. Mathematics, 2015, no. 1 (33). pp. 5–23.
- Romanov D. S., Romanova E. Yu. On the single fault detection test sets of constant cardinatity for generalized iterative switching circuits. Bulletin of the Moscow University. Computational Mathematics and Cybernetics, 2015, no. 3, pp. 42–50.
- Rychkov K. L. On the complexity of generalized contact circuits. Diskretn. Analiz and Issled. Oper., 2009, vol. 16, no. 5 , pp. 78–87.
- Chashkin A. V. On the Complexity of One System of Linear Boolean Functions. Moscow University Mathematics Bulletin, 2025, vol. 80, pp. 133–135. https://doi.org/10.3103/S0027132225700329
- Yablonskij S.V. Elements of mathematical cybernetics. Moscow: Higher School, 2007. 191 p.
- Cardot C. Quelques r`ezultats sur l’application de l’alg`ebre de Boole `a la synth`ese des circuits `a relais. Ann. Telecomm., 1952, vol. 7, no. 2, pp. 75–84.