окт 4
О соотношении между глубиной и сложностью монотонных булевых формул
И.С. Сергеев (НИИ «Квант»)
4 окт 2019 в 10:30
комната 220, корпус В
4 окт 2019 в 10:30
комната 220, корпус В
Построен пример последовательности монотонных булевых функций, глубина которых в базисе \( \{\vee,\wedge \}\) превосходит логарифм сложности реализации формулами в \(c > 1,06\) раз.