Замечание о задаче "Минимальное покрытие", соответствующей нижним оценкам сложности схем из функциональных элементов

Рассматриваются схемы из функциональных элементов в базисе $\{\vee,\wedge,\neg\}$ , при этом отрицания допускаются только на входах схемы. В статье [4] А. А. Разборовым доказано следующее утверждение. Пусть $f(x_1,\ldots,x_n)$ -- отличная от константы булева функция;

-- соответственно множество нулей и множество единиц этой функции; $X_i^{\epsilon}$ , где $\epsilon \in \{0,1\}$ -- множество вершин единичного

-мерного куба

, задаваемое уравнением $x_i=\epsilon$ . Для данного $\beta=(\beta_1,\ldots,\beta_n)\in N^1$ через ${\mathcal{F}}^\beta$ обозначим множество монотонно неубывающих функционалов $F:{\mathcal{P}}(N^0)\to \{0,1\}$ , действующих на множестве всех подмножеств множества

и удовлетворяющих условиям:

$\begin{displaymath} F(N^0\cap X_i^1)=\beta_i,\ F(N^0\cap X_i^0)=\beta_i\oplus 1;\ i=1,2,\ldots,n. \end{displaymath}$

Через ${\mathcal{F}}$ обозначим $\bigcup_{\beta\in N^1}{\mathcal{F}}^\beta$ . Каждой паре

, где $A,B\subseteq N^0$ , поставим в соответствие множество функционалов

$\begin{displaymath} \delta(A,B)\stackrel{\rm def}{\equiv} \{F\in {\mathcal{F}}\vert F(A)=F(B)=1, F(A\cap B)=0\}. \end{displaymath}$

Положим $\Delta \stackrel{\rm def}{\equiv} \{\delta(A,B)\vert A,B \subseteq N^0\}$ . Через $\tau({\mathcal{F}})$ обозначим мощность минимального покрытия множества ${\mathcal{F}}$ элементами из $\Delta$ . Пусть $L_{\wedge}(f)$ обозначает минимальное количество функциональных элементов $\wedge$ , необходимое для реализации функции

в указанном классе схем.

Теорема (Разборов). Справедливо неравенство

$\begin{displaymath} L_{\wedge}(f) \ge \tau({\mathcal{F}}). \end{displaymath}$

Приведенное утверждение доказывается в [4] при помощи метода апроксимаций, что обусловлено, по-видимому, целями статьи -- показать сильные и слабые стороны метода. Несомненно, данная теорема представляет интерес сама по себе, вне зависимости от метода апроксимаций. Кроме того, по-видимому, заслуживает внимания и "прямое", то есть без использования этого метода, доказательство теоремы, в частности, потому что оно более прозрачно. В настоящей работе теорема А.А. Разборова формулируется в несколько более общем виде и приводится ее "прямое" доказательство. Отметим, что это доказательство напоминает доказательство аналогичной теоремы для контактно-вентильных схем, приведенное тем же автором в [1]. Отметим также некоторые родственные мотивы, объединяющие указанные теоремы и аналогичную теорему В.М. Храпченко для параллельно-последовательных контактных схем (формул в базисе $\{\vee,\wedge,\neg\}$ ), см. [3,2]. Обобщение касается снятия части ограничений на множество функционалов ${\mathcal{F}}$ . Кроме того, утверждение теоремы Разборова дополняется аналогичным неравенством для $L _{\vee}(f)$ . А именно, для данного $\beta=(\beta_1,\ldots,\beta_n)\in N^1$ через ${\mathcal{F}}_{\wedge}^\beta$ обозначим множество отличных от константы монотонно неубывающих функционалов $F:{\mathcal{P}}(N^0)\to \{0,1\}$ , удовлетворяющих условиям:

$\begin{displaymath} F(N^0\cap X_i^{\beta_i})=1; \ i=1,2,\ldots,n. \end{displaymath}$

Через ${\mathcal{F}}_{\wedge}$ обозначим $\bigcup_{\beta\in N^1}{\mathcal{F}}_{\wedge}^{\beta}$ . Каждой паре

, где $A,B\subseteq N^0$ поставим в соответствие множество функционалов

$\begin{displaymath} \delta_{\wedge}(A,B)\stackrel{\rm def}{\equiv} \{F\in {\mathcal{F}}_{\wedge}\vert F(A)=F(B)=1, F(A\cap B)=0\}. \end{displaymath}$

Положим $\Delta_{\wedge} \stackrel{\rm def}{\equiv} \{\delta_{\wedge}(A,B)\vert A,B \subseteq N^0\}$ . Через $\tau({\mathcal{F}}_{\wedge})$ обозначим мощность минимального покрытия множества ${\mathcal{F}}_{\wedge}$ элементами из $\Delta_{\wedge}$ . Аналогично для данного $\alpha=(\alpha_1,\ldots,\alpha_n)\in N^0$ через ${\mathcal{F}}_{\vee}^\alpha$ обозначим множество отличных от константы монотонно невозрастающих функционалов $F:{\mathcal{P}}(N^1)\to \{0,1\}$ , удовлетворяющих условиям:

$\begin{displaymath} F(N^1\cap X_i^{\alpha_i\oplus 1})=1; \ i=1,2,\ldots,n. \end{displaymath}$

Через ${\mathcal{F}}_{\vee}$ обозначим $\bigcup_{\alpha\in N^0}{\mathcal{F}}_{\vee}^{\alpha}$ . Каждой паре

, где $C,D\subseteq N^1$ поставим в соответствие множество функционалов

$\begin{displaymath} \delta_{\vee}(C,D)\stackrel{\rm def}{\equiv} \{F\in {\mathcal{F}}_{\vee}\vert F(C)=F(D)=1, F(C\cup D)=0\}. \end{displaymath}$

Положим $\Delta_{\vee} \stackrel{\rm def}{\equiv} \{\delta_{\vee}(C,D)\vert C,D \subseteq N^1\}$ . Через $\tau({\mathcal{F}}_{\vee})$ обозначим мощность минимального покрытия множества ${\mathcal{F}}_{\vee}$ элементами из $\Delta_{\vee}$ .

Имеет место следующая Теорема. Справедливы неравенства

$\begin{displaymath} L_{\wedge}(f) \ge \tau({\mathcal{F}}_{\wedge}), \end{displaymath}$

$\begin{displaymath} L_{\vee}(f) \ge \tau({\mathcal{F}}_{\vee}). \end{displaymath}$

Литература

1: Разборов А.А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами // Математические заметки. 1990. Т. 48, вып. 6. С. 79-90.
2: Рычков К.Л. Модификация метода В.М. Храпченко и применение ее к оценкам сложности $\Pi$ -схем для кодовых функций // Дискретный анализ. Вып. 42. Новосибирск. 1985. С. 91-98.
3: Храпченко В.М. Об одном методе получения нижних оценок сложности $\Pi$ -схем // Математические заметки. 1971. Т. 10, 1. С. 83-92.
4: Razborov A.A. On the method of approximation// Proc. 21st ACM STOC. 1989. P. 167-176.

Ваши комментарии

[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Thursday, 20-Sep-2001 16:15:32 NOVST