Каков минимальный размер схемы, которая вычисляет PARITY?

21

Классический результат состоит в том, что каждая схема 2 вентилятора И-ИЛИ-НЕ, которая вычисляет PARITY из входных переменных, имеет размер не менее и это является резким. (Мы определяем размер как число логических элементов И и ИЛИ.) Доказательством является устранение гейта, и, похоже, оно потерпит неудачу, если мы допустим произвольный фан-ин. Чем известен этот случай?3(n1)

В частности, кто-нибудь знает пример, когда помогает больший фан-ин, т.е. нам нужно менее вентилей?3(n1)

Обновление 18 октября. Марцио показал, что для даже ворот, используя форму PARF в формате CNF. Это подразумевает оценку для общего . ВЫ можете сделать лучше?5 5n=35n52n2n

domotorp
источник
Эта статья может быть связана. Основание, однако, здесь намного больше, чем AND, OR.
Стасис
Следующий ответ (удаленно) связан с вашим вопросом. cstheory.stackexchange.com/questions/3624/…
Герман Грубер,
1
В обоих 3n и верхних границ, вы фактически игнорируя отрицаниявездеа не только от переменных,так ли? 52n
Эмиль Йержабек поддерживает Монику
1
Как это сделать, не дублируя ворота, если они используются как положительно, так и отрицательно?
Эмиль Йержабек поддерживает Монику
1
@Harry: Вам нужны вентиляционные ворота k-1, но их можно поместить в глубины k . Этот вопрос о РАЗМЕРЕ, а не ГЛУБИНЕ! logk
Домоторп

Ответы:

10

Можно рассчитать паритет, используя только ворота 2.33n + C. Конструкция довольно проста и приведена в этой статье.

http://link.springer.com/article/10.3103/S0027132215050083

Вот пример схемы для контроля четности 6 переменных, использующей только 12 вентилей (каждый вентиль является вентилем AND, кружок возле входа вентиля означает, что этот вход инвертирован). Обратите внимание, что схема для контроля четности из 6 переменных, которая построена путем суммирования блоков DNF (как в верхней границе Марцио), состоит из 13 элементов.

Я проверил, что для n = 2,3,4,5,6 размеры оптимальных схем составляют 3,5,8,10,12. Эти значения также являются размерами цепей, которые дают 2.33n верхней границы. Я до сих пор не знаю, является ли 2,33n размер оптимальной схемы для каждого n. Более того, я не знаю размера оптимальной схемы для четности 7 переменных (есть два возможных значения, 14 и 15). Схема для патити из 6 переменных

Юрий Комбаров
источник
10

Эта нижняя граница исключения из ворот не соответствует верхней границе Марцио, но это начало.

Предложение: Каждая неограниченная вычисляемая четность схемы И / ИЛИ / НЕ, вычисляющая четность по переменным, содержит как минимум 2 n - 1 логических элемента И и ИЛИ.n22n1

Для удобства я буду использовать модель, в которой единственными воротами являются И-ворота, но мы допускаем провода отрицания. Легко видеть, что для n = 2 необходимы элемента , поэтому достаточно показать, что если C - схема минимального размера, вычисляющая четность по n > 2 переменным, мы можем найти ограничение одной переменной, которое убивает по крайней мере двое ворот.3n=2Cn>2

xi0

aa=x1x2x1=0a=0Cx2x2b=¬x2c1crCcjx2x3,,xnx1=0cjx2¬x2Ccj1b¬x2a

2n152n2

[1] Инго Вегенер, Сложность функции четности в неограниченных разветвлениях, неограниченных схемах глубины , Теоретическая информатика 85 (1991), №. 1, с. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Эмиль Йержабек поддерживает Монику
источник
Да, поэтому вопрос в том, сможем ли мы устранить 5 вентилей, зафиксировав 2 переменные.
domotorp
n
8

Я расширяю свой комментарий:

kk1Ii2gi

|C|+i(Ii2)3(n1)

3(n1)(x1,x2,x3)

введите описание изображения здесь

Марцио де Биаси
источник
Хорошо, что для n = 3 у CNF всего 5 ворот! Интересно, можно ли вообще добиться большего.
domotorp
Я не особо задумывался об этом, но вы наверняка можете объединить и использовать параллельно вышеупомянутую схему и получить, например, схему PARITY для 9 переменных, которая использует только 20 вентилей вместо 24
Marzio De Biasi
Я сделал, и я обновил свой вопрос.
domotorp
2

5n/2

Если есть литерал с 3 родителями, мы можем исключить все 3 с одной переменной.

Если два литерала встречаются вместе в двух разных гейтах, то вместе мы можем применить основной аргумент из ответа Эмиля, снова удалив три вентиля с одной переменной.

domotorp
источник