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

В Булева алгебра, а функция четности это Логическая функция значение которого равно 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}$ обозначает Эксклюзивный или.

Свойства

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

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

Вычислительная сложность

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

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

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

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

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

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

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

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

похожие темы

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

Бит четности

использованная литература

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

Хостад, Йохан (1987), Вычислительные ограничения схем малой глубины (PDF), Кандидат наук. дипломная работа Массачусетского технологического института.CS1 maint: ref = harv (ссылка на сайт)

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

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

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

[4] Миклош Айтай " ${ displaystyle Sigma _ {1} ^ {1}}$ -Формулы конечных структур », Анналы чистой и прикладной логики, 24 (1983) 1–48.

[1]

[2]

[3]

[4]