Принципиальное расхождение между глубиной и задержкой

Ранее было показано, что даже у минимальной схемы задержка $T$ может быть значительно меньше глубины $D$. А именно, была построена бесконечная последовательность минимальных схем, у которых $T<\log_2D+6$, причем $D\to\infty$. Этот результат был бы убедительнее, если бы неравенство выполнялось и для всех эквивалентных минимальных схем. В настоящей работе построена бесконечная последовательность булевых функций $F_k$, $k=1,2,\dots$, такая, что всякая минимальная схема для любой функции $F_k$ имеет задержку и глубину, удовлетворяющие неравенству $T<\log_2D+14$.
Работа выполнена при поддержке Программы фундаментальных исследований ОПМ РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.