минимальная СФЭ

[cyb12]

Никак не получается доказать простую (вроде бы) вещь.
Есть система из двух булевых функций-конъюнкций $Q=\{x_1x_2\cdots x_n,\,x_1\overline x_2\cdots\overline x_n\}.$ Ее нужно реализовать схемой из функциональных элементов $\&,\,\vee,\,\neg$ с минимальной сложностью. Первое, что приходит на ум - первую из них непосредственно через $n-1$ конъюнкций, а вторую - сначала $n-2$ дизъюнкций для $x_2\vee\ldots \vee x_n$, потом от полученного отрицание и конъюнкцией с $x_1.$
Как доказать, что построенная так схема будет минимальной по числу элементов?
Кажется, что нужно показать, что каждая из $x_1,\ldots,x_n$ входит в СФЭ хотя бы 2 раза (для $x_1$ я смог это показать, вот как для остальных..?), и учесть, что без элемента отрицания не обойтись. Но нет ли другого, более адекватного способа?

[Xaositect]

Нижние оценки... Штука интересная, но нетривиальная.

В схеме есть немонотонная функция => есть отрицание, т.к. из конъюнкций и дизъюнкций строятся только монотонные функции.

Рассмотрим систему $\{x_1 x_2\dots x_n,\bar{x}_1\bar{x}_2\dots\bar{x}_n\}$. Докажем, что ее сложность не меньше $2n-1$.
Все отрицания поднимем к переменным и будем помечать каждую дугу, выходящую из переменной в зависимости от того, с отрицанием она берется или нет. Количество остальных элементов не изменится. Далее, от каждой переменной первая функция зависит монотонно, а вторая антимонотонно, значит, из каждой переменной выходит как минимум одна положительная дуга и одна отрицательная.
$2n$ существенных входов, $2$ выхода - значит, не менее $2n-2$ элементов. Вспоминаем про отрицание, получаем $2n-1$.

[cyb12]

Да, точно! Что-то ступил. Спасибо!

Xaositect в сообщении #418184 писал(а):

Нижние оценки... Штука интересная, но нетривиальная.

О да! Особенно при индивидуальном синтезе...

[cyb12]

Меня тут ночью осенило...

Xaositect в сообщении #418184 писал(а):

Все отрицания поднимем к переменным

Xaositect в сообщении #418184 писал(а):

Количество остальных элементов не изменится.

Но ведь это СФЭ. Если мы поднимаем отрицания, то число $\&,$ $\vee$ изменится. Ведь эквивалентные преобразования схем требуют тождества ветвления. Вот например, если есть схема, реализующая $\{x_1x_2,\,\overline{x_1x_2}\}$ следующим образом: 1 $\&$-элемент разветвляется на 1ый выход и элемент-отрицание, выход которого - 2ой выход. Тогда если поднять отрицания, то помимо $\&$ потребуется еще и $\vee.$ Или я не так понимаю "поднятие отрицания" ?

[Xaositect]

Упс, действительно. Значит, все-таки придется по индукции.

[Xaositect]

О, я вспомнил одну штуку. Это было у Шнорра.
Отрицания снова пока не считаем.
Рассмотрим элемент, обоими входами которого являются переменные или их отрицания. Подстановкой констант на место этих переменных мы на выходах этого элемента можем получить только два значения. Однако необходимо, чтобы подстановкой констант на место любых двух переменных мы получали три разных поведения - если $x_i = x_j = 0$, то на втором входе $\prod \bar{x}$, на первом 0, если $x_i = x_j = 1$, то на первом $\prod x$, на втором 0, если $x_i$ и $x_j$ различны, то на обоих нули. Это значит, что хотя бы один из входов $x_i$,$x_j$ соединен еще с одним элементом. Пусь $x_i$.
Теперь этот вход надо убрать и по индукции получить схему для меньшего числа переменных. Думаем, как это сделать.

[cyb12]

Xaositect в сообщении #418703 писал(а):

Рассмотрим элемент, обоими входами которого являются переменные или их отрицания.

Не понял фразу... Что это за элемент? Произвольный? Один из трех базисных? Или это вся схема?

[Xaositect]

cyb12 в сообщении #418714 писал(а):

Не понял фразу... Что это за элемент? Произвольный? Один из трех базисных? Или это вся схема?

Одна из "верхних" конъюнкций или дизъюнкций.

[cyb12]

Xaositect в сообщении #418703 писал(а):

Теперь этот вход надо убрать

Например, подставить 1 по тем дугам из $x_i,$ которые идут в $\&$, и 0 по тем, которые в $\vee$ (ну без учета отрицания)?

Xaositect в сообщении #418703 писал(а):

Это было у Шнорра.

Какую его работу вы имеете в виду?

[Xaositect]

cyb12 в сообщении #418721 писал(а):

Xaositect в сообщении #418703 писал(а):

Теперь этот вход надо убрать

Например, подставить 1 по тем дугам из $x_i,$ которые идут в $\&$, и 0 по тем, которые в $\vee$ (ну без учета отрицания)?

А почему при этом все получится, я что-то не догоняю?

Цитата:

Xaositect в сообщении #418703 писал(а):

Это было у Шнорра.

Какую его работу вы имеете в виду?

Не знаю, тут просто написано Schnorr 2n lower bound.

-- Вт мар 01, 2011 17:25:18 --

Вы знаете, я тут в Blue book нашел задачу:

Wegener, The Complexity of Boolean Functions писал(а):

12. Let $f_n(x) = x_1\dots x_n \vee \bar{x}_1\dots \bar{x}_n$ . By the elimination method one can prove only a lower bound of size $n + \Omega(1)$ . Try to prove larger lower bounds.

Очень похоже на нашу, и, видимо, нетривиально

[cyb12]

Xaositect в сообщении #418724 писал(а):

Blue book

Что Вы имеете в виду?

Xaositect в сообщении #418724 писал(а):

cyb12 в сообщении #418721 писал(а):

Xaositect в сообщении #418703 писал(а):

Теперь этот вход надо убрать

Например, подставить 1 по тем дугам из $x_i,$ которые идут в $\&$, и 0 по тем, которые в $\vee$ (ну без учета отрицания)?

А почему при этом все получится, я что-то не догоняю?

Ну тогда вроде получится схема для того же самого без $x_i,$ а удалится минимум 2 элемента. Или, наверное, я не прав?
Непонятно, как перейти к схеме от меньшего числа переменных...

[Xaositect]

cyb12 в сообщении #418742 писал(а):

Ну тогда вроде получится схема для того же самого без $x_i$

Вот именно это мне и не очевидно.

-- Вт мар 01, 2011 18:47:31 --

cyb12 в сообщении #418742 писал(а):

Что Вы имеете в виду?

Wegener, The Complexity of Boolean Functions

[cyb12]

(Оффтоп)

Xaositect в сообщении #418750 писал(а):

Wegener, The Complexity of Boolean Functions

О, такое есть) Как раз ее читаю, но до этого пока не дошел)

То, что я предложил, неверно, извиняюсь. Думаю, как же все-таки перейти.

[Xaositect]

Возможно, можно будет посчитать отдельно конъюнкции, отдельно дизъюнкции, если понять, какие из элементов по сути являются конъюнкциями, а какие дизъюнкциями. Это так, на уровне идеи.