Том 14, серия 1, номер 1, 2007 г., Стр. 110-139

УДК 519.72
Л. А. Шоломов
О сложности последовательной реализации частичных булевых функций схемами

Аннотация:
Пара $(f,g)$ частичных булевых функций характеризуется параметром $l_{\alpha,\beta}$ – числом наборов $\widetilde x$, на которых $(f(\widetilde x),g(\widetilde x))=(\alpha,\beta)$, где $\alpha$ и $\beta$ принимают значения 0, 1 и неопределённое. Рассматривается последовательная реализация системы $(f,g)$, когда сначала строится схема $S_f$ для $f$, которая затем достраивается до схемы $S_{f,g}$. Показано, что если область определения $D(f)$ включает $D(g)$, то можно последовательно реализовать $f$ и $g$ так, чтобы схемы $S_f$ и $S_{f,g}$ были одновременно асимптотически минимальными (т.е. удовлетворяли асимптотически наилучшим оценкам сложности для соответствующих классов), и что эти функции, вообще говоря, нельзя последовательно реализовать в порядке $g$, $f$, чтобы асимптотически минимальными были $S_g$ и $S_{f,g}$. Получена достижимая нижняя оценка сложности схем $S_{f,g}$ при последовательной реализации. Существенную роль играют информационные свойства частично определённых данных, изучение которых начато в предшествующих работах автора и продолжено здесь.
Библ. 12.

Шоломов Л. А. ¹
1. Институт системного анализа РАН,
проспект 60-летия Октября, 9, 117312 Москва, Россия
е-mail: sholomov@isa.ru

Статья поступила 14 октября 2006 г.