Классический результат состоит в том, что каждая схема 2 вентилятора И-ИЛИ-НЕ, которая вычисляет PARITY из входных переменных, имеет размер не менее и это является резким. (Мы определяем размер как число логических элементов И и ИЛИ.) Доказательством является устранение гейта, и, похоже, оно потерпит неудачу, если мы допустим произвольный фан-ин. Чем известен этот случай?
В частности, кто-нибудь знает пример, когда помогает больший фан-ин, т.е. нам нужно менее вентилей?
Обновление 18 октября. Марцио показал, что для даже ворот, используя форму PARF в формате CNF. Это подразумевает оценку для общего . ВЫ можете сделать лучше?5 ⌊ 5n
Ответы:
Можно рассчитать паритет, используя только ворота 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).
источник
Эта нижняя граница исключения из ворот не соответствует верхней границе Марцио, но это начало.
Для удобства я буду использовать модель, в которой единственными воротами являются И-ворота, но мы допускаем провода отрицания. Легко видеть, что для n = 2 необходимы элемента , поэтому достаточно показать, что если C - схема минимального размера, вычисляющая четность по n > 2 переменным, мы можем найти ограничение одной переменной, которое убивает по крайней мере двое ворот.3 п = 2 С n > 2
[1] Инго Вегенер, Сложность функции четности в неограниченных разветвлениях, неограниченных схемах глубины , Теоретическая информатика 85 (1991), №. 1, с. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4
источник
Я расширяю свой комментарий:
источник
Если есть литерал с 3 родителями, мы можем исключить все 3 с одной переменной.
Если два литерала встречаются вместе в двух разных гейтах, то вместе мы можем применить основной аргумент из ответа Эмиля, снова удалив три вентиля с одной переменной.
источник