И. С. Сергеев, “О соотношении между глубиной и сложностью монотонных булевых формул”, Дискретн. анализ и исслед. опер., 2019, том 26, выпуск 4,страницы 108

О соотношении между глубиной и сложностью монотонных булевых формул

И. С. Сергеев

Научно-исследовательский институт «Квант», 4-й Лихачёвский пер., 15, 125438 Москва, Россия

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

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

УДК: 519.7

Статья поступила: 26.12.2018
Переработанный вариант: 01.06.2019
Принята к публикации: 05.06.2019

DOI: 10.33048/daio.2019.26.643