Булева функция f : {0, 1}^n → {0, 1} называется симметрической, если ее значение не меняется при перестановке переменных. Докажите, что всякую симметрическую булеву функцию можно вычислить булевой схемой полиномиального от n размера.

задан 22 Янв '16 18:47

10|600 символов нужно символов осталось
0

Симметрическая б.ф. от $%n$% переменных задаётся при помощи $%n+1$% параметра: булевых значений $%a_0$%, $%a_1$%, ... , $%a_n$%, где $%a_k$% равно значению функции на наборе, в которых входит ровно $%k$% единиц из $%n$%.

Достаточно для каждой пары чисел $%0\le k\le n$% построить схему полиномиально зависящего от $%n$% размера, которая реализует булеву функцию $%f_{nk}(x_1,...,x_n)$%. Её значение равно 1 тогда и только тогда, когда единиц в наборе ровно $%k$%. После этого итоговая схема будет иметь вид $%a_0f_0\lor a_1f_1\lor\cdots\lor a_nf_n$%; её размер будет полиномиальным.

Пусть $%m$% -- минимальное число, для которого $%n < 2^m$%. Тогда все числа в пределах от 0 до $%n$% можно представлять в виде $%m$%-разрядного выражения, где $%m=O(\log n)$%. Опишем устройство "счётчика", который для каждого $%i$% от $%1$% до $%n$% подсчитывает количество единиц среди значений $%x_1,...,x_i$%, выдавая результат в форме $%m$%-разрядного двоичного числа, то есть $%m$% булевых функций.

Изначально все разряды равны нулю. Пусть на каком-то $%(i-1)$%-м шаге соответствующие схемы уже построены. Тогда мы прибавляем $%x_i$% к имеющемуся $%m$%-разрядному двоичному числу. Двоичный разряд меняется тогда и только тогда, когда прибавляется единица, и все цифры правее данного разряда равны 1. Это значит, что "текущий" $%j$%-й разряд, равный $%y_j$%, при нумерации от 1 до $%m$% справа налево, заменяется на $%y_j+y_{j-1}...y_1x_i$%, что для каждого из $%m$% разрядов требует порядка $%m$% элементов схемы. Поэтому сложность на каждом шаге будет иметь порядок $%m^2$%, а самих шагов будет порядка $%n$%. Тем самым, мы построим схему полиномиальной сложности (даже почти линейной), которая реализует описанный выше "счётчик".

Теперь можно размножить построенную схему в $%n$% копиях, и для $%k$%-й копии реализовать функцию $%f_{nk}$%. Для того, чтобы количество единиц в точности равнялось заданному $%k$%, требуется, чтобы показатели "счётчика" давали в точности двоичное представление $%k$%, то есть какие-то разряды равнялись единице, а какие-то нулю. Этому соответствует конъюнкция разрядов "счётчика" или их отрицаний, сложность которой имеет порядок $%m$%. Всё вместе даёт схему полиномиальной сложности.

ссылка

отвечен 23 Янв '16 12:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,326
×150
×26

задан
22 Янв '16 18:47

показан
1646 раз

обновлен
23 Янв '16 12:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru