Функция большинства

В булевой логике функция большинства ( также называемая оператором медианы ) — это булева функция , которая принимает значение «ложь», когда половина или более аргументов имеют значение «ложь», и «истина» в противном случае, т. е. значение функции равно значению большинства входных данных.

Булевы схемы

Мажоритарный вентиль — это логический вентиль, используемый в схемной сложности и других приложениях булевых схем . Мажоритарный вентиль возвращает значение true тогда и только тогда, когда более 50% его входов являются true.

Например, в полном сумматоре выходной перенос определяется путем применения функции большинства к трем входам, хотя часто эта часть сумматора разбивается на несколько более простых логических вентилей.

Многие системы имеют тройную модульную избыточность ; они используют функцию большинства для декодирования логики большинства с целью реализации исправления ошибок .

Основной результат в области сложности схем утверждает, что функция большинства не может быть вычислена с помощью схем AC0 субэкспоненциального размера.

Характеристики

Для любых x , y и z тернарный медианный оператор ⟨ x , y , z ⟩ удовлетворяет следующим уравнениям.

⟨ х , у , у ⟩ = у
⟨ х , у , z ⟩ = ⟨ z , x , y ⟩
⟨ х , у , z ⟩ = ⟨ х , z , у ⟩
⟨⟨ х , ш , у ⟩, ш , z ⟩ = ⟨ х , ш , ⟨ у , ш , z ⟩⟩

Абстрактная система, удовлетворяющая этим аксиомам, является медианной алгеброй .

Галстуки

Большинство приложений намеренно принудительно задают нечетное количество входов, чтобы не сталкиваться с вопросом, что произойдет, когда ровно половина входов равна 0, а ровно половина входов равна 1. Те немногие системы, которые вычисляют функцию большинства на четном количестве входов, часто смещены в сторону «0» — они выдают «0», когда ровно половина входов равна 0 — например, 4-входовой мажоритарный вентиль имеет выход 0 только тогда, когда на его входах появляются два или более 0. ^[1] В некоторых системах эта ничья может быть нарушена случайным образом. ^[2]

Монотонные формулы для большинства

Для n = 1 оператор медианы — это просто унарная операция тождества x . Для n = 3 оператор тернарной медианы можно выразить с помощью конъюнкции и дизъюнкции как xy + yz + zx .

Для произвольного n существует монотонная формула для большинства размера O( n ^5.3 ). Это доказывается вероятностным методом . Таким образом, эта формула неконструктивна. ^[3]

Существуют подходы для явной формулы для большинства размеров полиномов:

Возьмите медиану из сортировочной сети , где каждый сравнивающий-и-обменивающий "провод" - это просто вентиль ИЛИ и вентиль И. Конструкция Ajtai – Komlós – Szemerédi (AKS) является примером.
Объедините выходы меньших схем большинства. ^[4]
Дерандомизируйте доказательство Valiant монотонной формулы. ^[5]

Смотрите также

Примечания

^ Петерсон, Уильям Уэсли; Уэлдон, Э.Дж. (1972). Коды исправления ошибок . MIT Press. ISBN 9780262160391.
^ Chaouiya, Claudine; Ourrad, Ouerdia; Lima, Ricardo (июль 2013 г.). «Правила большинства со случайным разрешением ничьих в сетях регуляции булевых генов». PLOS ONE . 8 (7). Публичная научная библиотека: e69626. Bibcode : 2013PLoSO...869626C. doi : 10.1371/journal.pone.0069626 . PMC 3724945. PMID 23922761 .
^ Валиант, Лесли (1984). «Короткие монотонные формулы для функции большинства». Журнал алгоритмов . 5 (3): 363–366. doi :10.1016/0196-6774(84)90016-6.
^ Амано, Казуюки (2018). «Глубина двух мажоритарных схем для большинства и списочных расширителей». 43-й Международный симпозиум по математическим основам информатики (MFCS 2018) . 117 (81). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 1–13. doi : 10.4230/LIPIcs.MFCS.2018.81 .
^ Hoory, Shlomo; Magen, Avner; Pitassi, Toniann (2006). "Монотонные схемы для функции большинства". Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспект лекций по информатике. Том 4110. Springer. С. 410–425. doi :10.1007/11830924_38. ISBN 978-3-540-38044-3.

Ссылки

Кнут, Дональд Э. (2008). Введение в комбинаторные алгоритмы и булевы функции . Искусство программирования . Том 4а. Аппер Сэдл Ривер, Нью-Джерси: Addison-Wesley. С. 64–74. ISBN 978-0-321-53496-5.

Внешние ссылки

Медиа, связанные с функциями большинства на Wikimedia Commons