RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 1996, том 3, выпуск 3, страницы 40–46 (Mi da439)

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

Э. Ш. Коспанов

Институт математики им. С. Л. Соболева СО РАН

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

УДК: 621.391.7

Статья поступила: 05.06.1996



Реферативные базы данных:


© МИАН, 2024