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

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

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

Выходной сигнал функции четности - это бит четности .

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

Функция -переменной четности - это логическая функция со свойством, что тогда и только тогда, когда количество единиц в векторе нечетное. Другими словами, определяется следующим образом:${\ displaystyle n}$ ${\ Displaystyle f: \ {0,1 \} ^ {n} \ к \ {0,1 \}}$${\ displaystyle f (x) = 1}$ ${\ Displaystyle х \ в \ {0,1 \} ^ {п}}$${\ 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} клозов длины п . ^[1]   

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

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

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

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

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

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

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

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

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

похожие темы

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

Выход функции

• Бит четности

Статистическое свойство для независимых входов:

• Лемма о накоплении

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