About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:4, 746-752
Volume 26, No 4, 2019, P. 108-120
UDC 519.7
I. S. Sergeev
On a relation between the depth and complexity of monotone Boolean formulas
Abstract:
We present a sequence of monotone Boolean functions whose depth over the basis {$\lor, \land$} is $c > 1,06$ times greater than the logarithm of the formula complexity.
Tab. 1, bibliogr. 24.
Keywords: Boolean formula, depth, complexity, monotone function.
DOI: 10.33048/daio.2019.26.643
Igor S. Sergeev 1
1. Scientific and Research Institute «Kvant»,
15 Chetvyortyi Likhachyovskii Lane, 125438 Moscow, Russia
e-mail: isserg@gmail.com
Received December 26, 2018
Revised June 1, 2019
Accepted June 5, 2019
References
[1] M. I. Grinchuk, Sharpening an upper bound on the adder and comparator depths, Diskretn. Anal. Issled. Oper., Ser. 1, 15 (2), 12–22 (2008) [Russian] [J. Appl. Ind. Math. 3 (1), 61–67 (2009)].[2] R. F. Safin, On a relation between depth and complexity in precomplete classes of $k$-valued logic, in Mathematical Problems of Cybernetics, Vol. 13 (Fizmatlit, Moscow, 2004), pp. 223–278 [Russian].
[3] P. B. Tarasov, Conditions for the uniformity of systems of multivalued logic functions, Cand. Sci. Dissertation (Moscow State Univ., Moscow, 2016) [Russian].
[4] A. B. Ugol’nikov, Depth and polynomial equivalence of formulas for closed classes of two-valued logic, Mat. Zametki 42 (4), 603–612 (1987) [Russian] [Math. Notes 42 (4), 832–837 (1987)].
[5] V. M. Khrapchenko, Asymptotic estimate of addition time of a parallel adder, in Problems of Cybernetics, Vol. 19 (Nauka, Moscow, 1967), pp. 107–120 [Russian] [Syst. Theory Res. 19, 105–122 (1970)].
[6] V. M. Khrapchenko, On a relation between complexity and depth of formulas, in Methods of Discrete Analysis in Synthesis of Control Systems, Vol. 32 (Izd. Inst. Mat., Novosibirsk, 1978), pp. 76–94 [Russian].
[7] V. M. Khrapchenko, On a relation between complexity and depth of formulas in the basis containing median, in Methods of Discrete Analysis in Studying Boolean Functions and Graphs, Vol. 37 (Izd. Inst. Mat., Novosibirsk, 1981), pp. 77–84 [Russian].
[8] S. V. Yablonskii and V. P. Kozyrev, Mathematical problems of cybernetics, in Information Materials of Scientific Council of Academy of Sciences USSR on Complex Problem “Cybernetics”, Vol. 19a (Akad. Nauk USSR, Moscow, 1968), pp. 3–15 [Russian].
[9] S. V. Yablonskii, Introduction to Discrete Mathematics (Nauka, Moscow, 1986) [Russian].
[10] A. Barak and E. Shamir, On the parallel evaluation of Boolean expressions, SIAM J. Comput. 5 (4), 678–681 (1976).
[11] R. P. Brent, D. J. Kuck, and K. Maruyama, The parallel evaluation of arithmetic expressions without division, IEEE Trans. Comp. C-22, 532–534 (1973).
[12] R. P. Brent, The parallel evaluation of general arithmetic expressions in logarithmic time, J. ACM 21 (2), 201–206 (1974).
[13] B. Commentz-Walter, Size-depth tradeoff in monotone Boolean formulae, Acta Inform. 12, 227–243 (1979).
[14] B. Commentz-Walter and J. Sattler, Size-depth tradeoff in nonmonotone Boolean formulae, Acta Inform. 14, 257–269 (1980).
[15] D. Coppersmith and B. Schieber, Lower bounds on the depth of monotone arithmetic computations, in Proc. 33rd Symp. Found. Comput. Sci. (IEEE CS, Washington, 1992), pp. 288–295.
[16] S. R. Kosaraju, Parallel evaluation of division-free arithmetic expressions, in Proc. 18th Annu. ACM Symp. Theory Comput. (ACM, New York, 1986), pp. 231–239.
[17] W. F. McColl, Some results on circuit depth. Theory of computation, Report No. 18, (Univ. of Warwick, Coventry, 1977).
[18] D. E. Muller and F. P. Preparata, Restructuring of arithmetic expressions for parallel evaluation, J. ACM 23 (3), 534–543 (1976).
[19] F. P. Preparata and D. E. Muller, The time required to evaluate division-free arithmetic expressions, Inf. Proc. Lett. 3 (5), 144–146 (1975).
[20] F. P. Preparata and D. E. Muller, Efficient parallel evaluation of Boolean expressions, IEEE Trans. Comp. C-25 (5), 548–549 (1976).
[21] F. P. Preparata, D. E. Muller, and A. B. Barak, Reduction of depth of Boolean networks with a fan-in constraint, IEEE Trans. Comp. C-26 (5), 474–479 (1977).
[22] M. Ragaz, Parallelizable algebras, Arch. Math. Logic 26, 77–99 (1986/87).
[23] E. Shamir and M. Snir, On the depth complexity of formulas, Math. Syst. Theory 13 (4), 301–322 (1979/80).
[24] P. M. Spira, On time-hardware complexity tradeoffs for Boolean functions, in Proc. Hawaii Symp. Syst. Sci. (Western Periodical Company, N. Hollywood, 1971), pp. 525–527.
