О соотношении времени вычисления прямого и обратного отображений

Пусть $S$ есть перестановка множества всех $(0,1)$-векторов длины $n$, а $P^{-1}$ – ей обратная. Показано,что минимально-возможная глубина схемы из функциональных элементов в базисе $\{\&,\vee,^-\}$, реализующей систему булевых функций, определяемую перестановкой $P$, может отличаться от минимально- возможной глубины схемы, реализующей систему булевых функций, определяемую перестановкой $P^{-1}$, не менее чем на $2\log_2n-3$, а для почти всех рассматриваемых перестановок эта разница не превышает 4.
Библиогр. 11