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

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

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

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

Определение [ править ]

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

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

где $\oplus$ обозначает исключительный или .

Свойства [ править ]

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

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

Вычислительная сложность [ править ]

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

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

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

Бесконечная версия [ править ]

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

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

Бесконечные функции четности часто используются в теоретической информатике и теории множеств из-за их простоты определения и, с другой стороны, их описательной сложности. Например, можно показать, что прообраз $f^{-1}[0]$ является неборелевским множеством .

См. также [ править ]

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

Связанные темы:

Ссылки [ править ]

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

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

[wp-1] Инго Вегенер , Рэндалл Дж. Прюим, Теория сложности , 2005, ISBN 3-540-21045-8 , с. 260

[jukna-2] Юкна, Стасис (6 января 2012 г.). Сложность булевых функций: достижения и границы . Springer Science & Business Media. стр. 167–173. ISBN 978-3642245084 .

[FSS-3] Jump up to: ^а ^б Меррик Ферст, Джеймс Сакс и Майкл Сипсер, «Четность, схемы и иерархия полиномиального времени», Annu. Международный Симп. Найдено.Информатика, 1981, Теория вычислительных систем , вып. 17, нет. 1, 1984, стр. 13–27, два : 10.1007/BF01744431

[4] Миклош Айтай, " $\Sigma _{1}^{1}$ -Формулы конечных структур», Annals of Pure and Applied Logic , 24 (1983) 1–48.

[1]

[2]

[3]

[4]