Том 3, номер 3, 1996 г., Стр. 40-46

УДК 621.391.7
Э. Ш. Коспанов
О соотношении времени вычисления прямого и обратного отображений

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

Коспанов Э. Ш. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 5 июня 1996 г.