Количество двоичных элементов, необходимых для одновременного вычисления И и ИЛИ из n входных битов

Какое минимальное количество двоичных вентилей необходимо для вычисления И и ИЛИ из входных битов одновременно? Тривиальная верхняя граница . Я считаю, что это оптимально, но как это доказать? Стандартный метод устранения строба здесь не работает, так как, присваивая константу любой из входных переменных, можно тривиализировать один из выходных данных. $n$ $2n-2$

Эта проблема также приводится в упражнении 5.12 в книге Инго Вегенера «Сложность булевых функций» в несколько иной форме: «Пусть . Методом исключения можно доказать только нижнюю границу размера . Попробуйте доказать большие нижние оценки. " $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$ $n+\Omega(1)$

cc.complexity-theory lower-bounds circuit-complexity Александр Сергеевич Куликов
источник

@Ryan: Вопрос не о том и в OR , а о И и ИЛИ. Хотя я не знаю ответа на вопрос Саши.

Цуёси Ито

@TsuyoshiIto Спасибо, каким-то образом мне удалось разобрать его неправильно. Это определенно нетривиальная проблема - можно было бы использовать другие виды ворот, чтобы получить преимущество над

2 n - 2

$2n-2$

Райан Уильямс

@ Саша, вы пробовали применять SAT-решатели к небольшим примерам (например,

), как в некоторых из ваших предыдущих работ?

n = 4

$n=4$

Райан Уильямс

@ Райан Да, конечно. Мы знаем, что

. Это для функции из книги (это

если все

входных битов равны). Это растет как

. И схему размера

легко построить: сначала вычислим

для всех

C_{3} = 3

$C_3=3$

C_{4} = 5

$C_4=5$

C_{5} \leq 7

$C_5 \le 7$

1

$1$

n

$n$

2 n - 3

$2n-3$

2 n - 3

$2n-3$

x_{i} \equiv x_{i + 1}

$x_i \equiv x_{i+1}$

(

вентилей), а затем вычислить их соединение (

вентилей).

i = 1, \dots, n - 1

$i=1,\dots,n-1$

(n - 1)

$(n-1)$

(n - 2)

$(n-2)$

Александр Сергеевич Куликов

@Tsuyoshi: Я думаю , что

ворот функционируют Саша является второй функцией вопроса (

) , которые могут быть построены с

вентиль XNOR (применяется к

) и

вентиль AND применяется к XNOR.

2 n - 3

$2n-3$

f_{n} (x) = x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$

n - 1

$n-1$

x_{i}, x_{i + 1}

$x_i,x_{i+1}$

n - 2

$n-2$

Марцио Де Биаси

Ответы:

Эта статья Blum & Seysen может быть полезна:

Н. Блюм, М. Сейсен. Характеристика всех оптимальных сетей для одновременного вычисления AND и NOR . Acta Inf. 21: 171-181 (1984)

Я подумал , что для нижняя граница может быть получена с помощью методов Blum & Seysen, но мне кажется , что это не так. $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$

Владимир Лысиков
источник

Существует ли общедоступная PDF-версия статьи Блюма и Сейзена?

Марцио Де Биаси

@ Владимир, спасибо за ссылку! Я постараюсь проверить, применимы ли их методы в этом случае, когда найду статью.

Александр Сергеевич Куликов

@ Владимир, еще раз спасибо! На самом деле, эта статья содержит именно тот ответ на мой вопрос и даже больше: он говорит, что для вычисления И и ИЛИ одновременно нужно

и любая схема такого размера вычисляет И и ИЛИ независимо (это интересно!). Также нетрудно показать, что

2 n - 2

$2n-2$

C (f_{n}) \geq C (A N D, O R) - c \geq 2 n - c^{'}

$C(f_n) \ge C(AND,OR)-c \ge 2n-c'$

Александр Сергеевич Куликов

@Sasha, yes, I missed this simple construction. To clarify things, in the paper AND and NOR functions are considered, so for AND and OR we get

2 n - 2

$2n-2$ lower bound by altering one gate and for

x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$ ---

2 n - 5

$2n-5$

Vladimir Lysikov

Just a reminder @SashaK. if you like the answer, please "accept" it by clicking on the tick mark below the vote count.

Suresh Venkat

$3\lfloor n/2 \rfloor$ .

The clever algorithm proving the upper bound translates to an AND/OR circuit with same bound you get, since one of the comparisons computes both a minimum and a maximum.

However, the lower bound (given by an adversary argument) does seem to translate, at least in the case of monotone circuits (since an AND/OR circuit translates to a max/min algorithm). This would imply a lower bound of $3\lfloor n/2 \rfloor$ . Perhaps a tight lower bound can be obtained by analyzing the adversary argument.

The upper bound appears in "Introduction to Algorithms", where you can also find the easy argument showing that max/min comparator circuits are valid iff they work for boolean inputs (use an appropriate threshold). The lower bound can be found e.g. here.

Yuval Filmus
источник

Note in Sasha's question, all 2-bit Boolean functions can be used to construct the circuit.

Ryan Williams

Yes, it is not clear how the lower bound can be translated to the case of all binary functions.

Alexander S. Kulikov