Постройте схему полиномиального размера, вычисляющую функцию $%MAJ$%. Функция $%MAJ(x_1, . . , x_n)=1$% тогда и только тогда, когда сумма всех $%x_i > \frac n2$%.

задан 29 Янв '15 2:00

изменен 29 Янв '15 19:26

falcao's gravatar image


193k1632

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

Возможно, имеет смысл разобрать отдельно этот более простой вариант задачи, когда в качестве элементов схем допускается использование отрицания, так как уже он достаточно нетривиален. Позже можно будет обсудить усложнённую версию.

Идея следующая: подсчитать количество единиц массива, записав это число в двоичном виде. Ответ будет иметь $%m$% разрядов, где $%m$% имеет порядок $%\log n$%. Фактически это означает, что создаётся $%m$% схем -- для каждого из разрядов по отдельности. После того, как эти схемы созданы, нужно сравнить найденное число с двоичным представлением числа $%[n/2]$%. Последнее также есть $%m$%-разрядное двоичное число, которым мы непосредственно располагаем. Если первое число равно $%\overline{a_1\ldots a_m}$%, а второе равно $%\overline{b_1\ldots b_m}$%, то мы хотим получить 0 на выходе, если первое число не превосходит второго, и 1 в противном случае.

Формула, дающая требуемый результат (а также соответствующая схема) имеет такой вид: $%(a_1 > b_1)\lor(a_1=b_1)\&((a_2 > b_2)\lor(a_2=b_2)\&(\cdots)\ldots)$%, где детали довольно легко восстановить. Отношения "больше", а также "равно" несложно выражаются через основные логические операции. Соответствующая схема сравнения имеет размер порядка $%\log n$%, то есть он совсем небольшой.

Теперь опишем принцип подсчёта количества единиц массива. Разделим массив примерно пополам (для массивов длины 1 всё ясно, так как ответом будет $%x_1$%). Для каждой из половин создаём (по рекурсии) схему, подсчитывающую число единиц в этой части массива. Фактически, мы для каждой из половин имеем $%(m-1)$%-разрядное число, и теперь надо эти два числа сложить, получая $%m$%-разрядное число, которое и будет ответом.

Алгоритм сложения двух чисел с заданным числом разрядов аналогичен тому, каким мы пользуемся в десятичной арифметике. В данном случае он ещё проще. Пусть у нас имеются числа $%\overline{a_1\ldots a_{m-1}}$% и $%\overline{b_1\ldots b_{m-1}}$%; надо найти их сумму $%\overline{c_1\ldots c_m}$%, строя соответствующие схемы. Этот алгоритм достаточно хорошо известен, и он во всех деталях описан в литературе (в частности, у Дональда Кнута, где подсчитывается его сложность в виде числа выполняемых операций). Ясно, что $%c_m=a_{m-1}\oplus b_{m-1}$%, а в следующий разряд переходит произведение $%d_{m-1}=a_{m-1}b_{m-1}$%. Далее получается $%c_{m-1}=a_{m-2}\oplus b_{m-2}\oplus d_{m-1}$%, и нетрудно в явном виде выразить число $%d_{m-2}$%, переходящее в следующий разряд; и так далее. Ясно, что данная процедура требует полиномиального числа операций относительно $%m=\log n$%, то есть она достаточно быстрая. Можно дать более явную оценку, но я предпочитаю опустить эти детали.

Так или иначе, общее число $%f(n)$% элементов схемы, которое нам нужно для суммирования элементов массива длиной $%n$%, удовлетворяет неравенству $%f(n)\le2f(n/2)+O(\log^cn)$%, где $%c$% -- некоторая константа. Отсюда легко выводится, что $%f(n)$% ограничено сверху полиномом. Если не искать "оптимальной" точности, то заведомо годится оценка $%O(n^2)$%.

ссылка

отвечен 29 Янв '15 23:00

@falcao, Подскажите, пожалуйста, как построить такую схему полиномиального размера но в монотонном базисе {∧, ∨}, то есть как избавиться от XOR, или от эквивалентности, которая является отрицанием к XOR

(27 Янв '16 1:09) laminat

@plitka: это отдельная задача, и она, скорее всего, требует отдельного разбора. Я над ней не думал, и сходу мне ничего не сказать. Имеет смысл оформить её как отдельный вопрос.

(27 Янв '16 1:26) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×131

задан
29 Янв '15 2:00

показан
579 раз

обновлен
27 Янв '16 1:26

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

по почте:

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

по RSS:

Ответы

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

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