Функция четности

В булевой алгебре функция четности — это булева функция , значение которой равно единице тогда и только тогда, когда входной вектор имеет нечетное число единиц. Функция четности двух входов также известна как функция XOR .

Функция четности примечательна своей ролью в теоретическом исследовании сложности схем булевых функций.

Выходным значением функции четности является бит четности .

Определение

Функция четности переменной - это булева функция со свойством, что если и только если число единиц в векторе нечетно. Другими словами, определяется следующим образом: ${\displaystyle n}$ ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle f(x)=1}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle f}$

${\displaystyle f(x)=x_{1}\oplus x_{2}\oplus \dots \oplus x_{n}}$

где обозначает исключающее или . ${\displaystyle \oplus }$

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

Четность зависит только от количества единиц и поэтому является симметричной булевой функцией .

Функция четности n -переменной и ее отрицание являются единственными булевыми функциями, для которых все дизъюнктивные нормальные формы имеют максимальное число 2 ^{n  − 1} мономов длины n , а все конъюнктивные нормальные формы имеют максимальное число 2 ^{n  − 1} предложений длины n . ^[1]   

Сложность вычислений

Одной из самых ранних работ по вычислительной сложности была работа Беллы Субботовской 1961 года, показывающая , что размер булевой формулы, вычисляющей четность, должен быть не менее . В этой работе используется метод случайных ограничений. Этот показатель степени был увеличен путем тщательного анализа до Патерсона и Цвика (1993), а затем до Хастада ( 1998). ^[2] ${\displaystyle O(n^{3/2})}$ ${\displaystyle 3/2}$ ${\displaystyle 1.63}$ ${\displaystyle 2}$

В начале 1980-х годов Меррик Фёрст, Джеймс Сакс и Майкл Сипсер ^[3] и независимо Миклош Айтай ^[4] установили суперполиномиальные нижние границы размера булевых схем постоянной глубины для функции четности, т. е. они показали, что схемы полиномиального размера постоянной глубины не могут вычислить функцию четности. Аналогичные результаты были также установлены для функций большинства, умножения и транзитивного замыкания путем редукции из функции четности. ^[3]

Хастад (1987) установил точные экспоненциальные нижние границы размера булевых схем постоянной глубины для функции четности. Лемма о переключении Хастада является ключевым техническим инструментом, используемым для этих нижних границ, и Йохан Хастад был награжден премией Гёделя за эту работу в 1994 году. Точный результат заключается в том, что схемы глубиной k с вентилями И, ИЛИ и НЕ требуют размера для вычисления функции четности. Это асимптотически почти оптимально, поскольку существуют схемы глубиной k , вычисляющие четность, которые имеют размер . ${\displaystyle \exp(\Omega (n^{\frac {1}{k-1}}))}$ ${\displaystyle \exp(O(n^{\frac {1}{k-1}})t)}$

Бесконечная версия

Бесконечная функция четности — это функция, отображающая каждую бесконечную двоичную строку в 0 или 1, обладающая следующим свойством: если и — бесконечные двоичные строки, отличающиеся только конечным числом координат, то тогда и только тогда, когда и отличаются четным числом координат. ${\displaystyle f\colon \{0,1\}^{\omega }\to \{0,1\}}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle f(w)=f(v)}$ ${\displaystyle w}$ ${\displaystyle v}$

Предполагая аксиому выбора , можно доказать, что функции четности существуют и их много; столько же, сколько и всех функций из в . Достаточно взять по одному представителю на класс эквивалентности отношения, определяемого следующим образом: если и отличаются на конечное число координат. Имея таких представителей, мы можем отобразить их все в ; остальные значения выводятся однозначно. ${\displaystyle 2^{2^{\aleph _{0}}}}$ ${\displaystyle \{0,1\}^{\omega }}$ ${\displaystyle \{0,1\}}$ ${\displaystyle \approx }$ ${\displaystyle w\approx v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle 0}$ ${\displaystyle f}$

Другое построение бесконечной функции четности можно осуществить с помощью неглавного ультрафильтра на . Существование неглавных ультрафильтров на следует из аксиомы выбора и является строго слабее ее. Для любого мы рассматриваем множество . Бесконечная функция четности определяется отображением в тогда и только тогда, когда является элементом ультрафильтра. ${\displaystyle U}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle w:\omega \to \{0,1\}}$ ${\displaystyle A_{w}=\{n\in \omega \mid \{k\leq n\mid w(k)=0\}{\text{ is even}}\}}$ ${\displaystyle f}$ ${\displaystyle w}$ ${\displaystyle 0}$ ${\displaystyle A_{w}}$

Необходимо предположить по крайней мере некоторое количество выбора, чтобы доказать, что существуют бесконечные функции четности. Если — бесконечная функция четности, и мы рассматриваем прообраз как подмножество пространства Кантора , то — неизмеримое множество и не обладает свойством Бэра . Без аксиомы выбора последовательно (относительно ZF ), что все подмножества пространства Кантора измеримы и обладают свойством Бэра, и, таким образом, не существует бесконечной функции четности; это справедливо , например, в модели Соловея . ${\displaystyle f}$ ${\displaystyle f^{-1}[0]}$ ${\displaystyle \{0,1\}^{\omega }}$ ${\displaystyle f^{-1}[0]}$

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

• Функция Уолша , непрерывный эквивалент
• Бит четности , выход функции
• Лемма о накоплении , статистическое свойство для независимых входов
• Многоканальное переключение , физическая реализация, часто используемая для управления освещением.

Похожие темы:

• Исправление ошибок
• Обнаружение ошибок

Ссылки

1. Инго Вегенер , Рэндалл Дж. Прюим, Теория сложности , 2005, ISBN 3-540-21045-8 , стр. 260  
2. Jukna, Stasys (6 января 2012 г.). Сложность булевых функций: достижения и рубежи . Springer Science & Business Media. стр. 167–173. ISBN 978-3642245084.
3. Merrick Furst, James Saxe и Michael Sipser, "Четность, схемы и иерархия полиномиального времени", Annu. Intl. Symp. Found. Computer Sci., 1981, Теория вычислительных систем , т. 17, № 1, 1984, стр. 13–27, doi :10.1007/BF01744431
4. Миклош Айтай, « Формулы конечных структур», Annals of Pure and Applied Logic , 24 (1983) 1–48. ${\displaystyle \Sigma _{1}^{1}}$

• Хастад, Йохан (1987), Вычислительные ограничения схем малой глубины (PDF) , докторская диссертация, Массачусетский технологический институт.