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

В Логическая логика, то функция большинства (также называемый медианный оператор) это функция из п входы к одному выходу. Значение операции ложно, когда п/ 2 или более аргументов являются ложными, в противном случае - истиной. В качестве альтернативы, представляя истинные значения как 1 и ложные значения как 0, мы можем использовать формулу

{displaystyle langle p_ {1}, dots, p_ {n} angle = operatorname {Majority} left (p_ {1}, dots, p_ {n} ight) = leftlfloor {frac {1} {2}} + {frac { left (сумма _ {i = 1} ^ {n} p_ {i} ight) -1/2} {n}} ightfloor.}

«−1/2» в формуле служит для разрыва связей в пользу нулей, когда п даже. Если термин «-1/2» опущен, формула может использоваться для функции, которая прерывает связи в пользу единиц.

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

Булевы схемы

Трехразрядная мажоритарная схема

Четырехбитная мажоритарная схема

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

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

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

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

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

Для любого Икс, у, и z, тернарный медианный оператор ⟨Икс, у, z⟩ Удовлетворяет следующим уравнениям.

⟨Икс, у, у⟩ = у
⟨Икс, у, z⟩ = ⟨z, Икс, у⟩
⟨Икс, у, z⟩ = ⟨Икс, z, у⟩
⟨⟨Икс, ш, у⟩, ш, z⟩ = ⟨Икс, ш, ⟨у, ш, z⟩⟩

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

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

За п = 1 медианный оператор - это просто унарная тождественная операция Икс. За п = 3 тернарный медианный оператор может быть выражен с помощью конъюнкции и дизъюнкции как ху + yz + zx. Примечательно, что это выражение обозначает ту же операцию независимо от того, интерпретируется ли символ + как включительно или или же Эксклюзивный или.

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

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

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

Примечания

^ Петерсон, Уильям Уэсли; Велдон, Э.Дж. (1972). Коды с исправлением ошибок. MIT Press. ISBN 9780262160391.
^ Чауйя, Клодин; Уррад, Уэрдия; Лима, Рикардо (июль 2013 г.). «Правила большинства со случайным разрывом связей в регулирующих сетях логических генов». PLoS ONE. 8 (7). Публичная научная библиотека. Дои:10.1371 / journal.pone.0069626.
^ Доблестный, Лесли (1984). «Краткие монотонные формулы для функции большинства». Журнал алгоритмов. 5 (3): 363–366. Дои:10.1016/0196-6774(84)90016-6.
^ Амано, Казуюки (2018). «Глубина двух схем большинства для большинства и расширителей списка». 43-й Международный симпозиум по математическим основам информатики (MFCS 2018). Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 117 (81): 1–13. Дои:10.4230 / LIPIcs.MFCS.2018.81.
^ Хори, Шломо; Маген, Авнер; Питасси, Тониан (2006). «Монотонные схемы для функции большинства». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Springer: 410–425. Дои:10.1007/11830924_38.

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

СМИ, связанные с Функции большинства в Wikimedia Commons

[1] Петерсон, Уильям Уэсли; Велдон, Э.Дж. (1972). Коды с исправлением ошибок. MIT Press. ISBN 9780262160391.

[2] Чауйя, Клодин; Уррад, Уэрдия; Лима, Рикардо (июль 2013 г.). «Правила большинства со случайным разрывом связей в регулирующих сетях логических генов». PLoS ONE. 8 (7). Публичная научная библиотека. Дои:10.1371 / journal.pone.0069626.

[3] Доблестный, Лесли (1984). «Краткие монотонные формулы для функции большинства». Журнал алгоритмов. 5 (3): 363–366. Дои:10.1016/0196-6774(84)90016-6.

[4] Амано, Казуюки (2018). «Глубина двух схем большинства для большинства и расширителей списка». 43-й Международный симпозиум по математическим основам информатики (MFCS 2018). Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 117 (81): 1–13. Дои:10.4230 / LIPIcs.MFCS.2018.81.

[5] Хори, Шломо; Маген, Авнер; Питасси, Тониан (2006). «Монотонные схемы для функции большинства». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Springer: 410–425. Дои:10.1007/11830924_38.

[1]

[2]

[3]

[4]

[5]