Том 26, номер 4, 2019 г., Стр. 108-120

УДК 519.7
Сергеев И. С.
О соотношении между глубиной и сложностью монотонных булевых формул

Аннотация:
Построен пример последовательности монотонных булевых функций, глубина которых в базисе {$\lor, \land$} превосходит логарифм сложности реализации формулами в $c > 1,06$ раз.
Табл. 1, библиогр. 24.

Ключевые слова: булевы формулы, глубина, сложность, монотонные функции.

DOI: 10.33048/daio.2019.26.643

Сергеев Игорь Сергеевич ¹
1. Научно-исследовательский институт «Квант»,
4-й Лихачёвский пер., 15, 125438 Москва, Россия
е-mail: isserg@gmail.com

Статья поступила 26 декабря 2018 г.
После доработки — 1 июня 2019 г.
Принята к публикации 5 июня 2019 г.

Литература

[1] Гринчук М. И. Уточнение верхней оценки глубины сумматора и компаратора // Дискрет. анализ и исслед. операций. Сер. 1. 2008. Т. 15, № 2. C. 12–22.

[2] Сафин Р. Ф. О соотношении между глубиной и сложностью в предполных классах $k$-значной логики // Мат. вопросы кибернетики. Вып. 13. М.: Физматлит, 2004. C. 223–278.

[3] Тарасов П. Б. Об условиях равномерности систем функций многозначной логики: Дисс. . . . канд. физ.-мат. наук. М.: МГУ, 2016.

[4] Угольников А. Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Мат. заметки. 1987. Т. 42, № 4. C. 603–612.

[5] Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора // Пробл. кибернетики. Вып. 19. М.: Наука, 1967. C. 107–120.

[6] Храпченко В. М. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем. Вып. 32. Новосибирск: Ин-т математики СО АН СССР, 1978. C. 76–94.

[7] Храпченко В. М. О соотношении между сложностью и глубиной формул в базисе, содержащем медиану // Методы дискретного анализа в изучении булевых функций и графов. Вып. 37. Новосибирск: Ин-т математики СО АН СССР, 1981. C. 77–84.

[8] Яблонский С. В., Козырев В. П. Математические вопросы кибернетики // Инф. мат. Науч. совета по комплексной проблеме «Кибернетика» АН СССР. М., 1968. Вып. 19а. C. 3–15.

[9] Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

[10] Barak A., Shamir E. On the parallel evaluation of Boolean expressions // SIAM J. Comput. 1976. Vol. 5, No. 4. P. 678–681.

[11] Brent R. P., Kuck D. J., Maruyama K. The parallel evaluation of arithmetic expressions without division // IEEE Trans. Comp. 1973. Vol. C-22. P. 532–534.

[12] Brent R. P. The parallel evaluation of general arithmetic expressions in logarithmic time // J. ACM. 1974. Vol. 21, No. 2. P. 201–206.

[13] Commentz-Walter B. Size-depth tradeoff in monotone Boolean formulae // Acta Inf. 1979. Vol. 12. P. 227–243.

[14] Commentz-Walter B., Sattler J. Size-depth tradeoff in non-monotone Boolean formulae // Acta Inf. 1980. Vol. 14. P. 257–269.

[15] Coppersmith D., Schieber B. Lower bounds on the depth of monotone arithmetic computations // Proc. 33rd Symp. Found. Comput. Sci. Washington: IEEE CS, 1992. P. 288–295.

[16] Kosaraju S. R. Parallel evaluation of division-free arithmetic expressions // Proc. 18th ACM Symp. Theory Comput. New York: ACM, 1986. P. 231–239.

[17] McColl W. F. Some results on circuit depth. Theory of computation. Rep. No. 18. Coventry: Univ. Warwick, 1977.

[18] Muller D. E., Preparata F. P. Restructuring of arithmetic expressions for parallel evaluation // J. ACM. 1976. Vol. 23, No. 3. P. 534–543.

[19] Preparata F. P., Muller D. E. The time required to evaluate division-free arithmetic expressions // Inf. Proc. Lett. 1975. Vol. 3, No. 5. P. 144–146.

[20] Preparata F. P., Muller D. E. Efficient parallel evaluation of Boolean expressions // IEEE Trans. Comp. 1976. Vol. C-25, No. 5. P. 548–549.

[21] Preparata F. P., Muller D. E., Barak A. B. Reduction of depth of Boolean networks with a fan-in constraint // IEEE Trans. Comp. 1977. Vol. C-26, No. 5. P. 474–479.

[22] Ragaz M. Parallelizable algebras // Arch. Math. Logic. 1986/87. Vol. 26. P. 77–99.

[23] Shamir E., Snir M. On the depth complexity of formulas // Math. Syst. Theory. 1979/80. Vol. 13, No. 4. P. 301–322.

[24] Spira P. M. On time-hardware complexity tradeoffs for Boolean functions // Proc. 4th Hawaii Symp. System Sci. N. Hollywood: Western Periodical Co., 1971. P. 525–527.