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

И.С. Сергеев (НИИ «Квант»)
4 окт 2019 в 10:30
комната 220, корпус В

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


gpEasy-Theme simplicity 1.5 by syndicatefx