Постройте схему полиномиального размера в монотонном базисе {∧, ∨}, вычисляющую функцию MAJ(x1, . . . , xn).

задан 27 Янв '16 1:36

1

наверное, надо написать, что такое $%\mathrm MAJ$%

(27 Янв '16 9:57) Trumba

@Trumba: я постоянно выступаю за то, чтобы все "локальные" термины сопровождались определениями в тексте вопросов. Это как бы следование "правилам хорошего тона". Тем более, что одни и те же вещи здесь могут называться или обозначаться по-разному. Правда, в данном случае функция MAJ является частым "гостем" на форуме -- она фигурировала во многих задачах. Здесь имеется в виду, что значение функции равно значению большинства переменных (majority). Хотя для случая чётного n полезно было бы оговорить, что будет при условии "ничьей".

(27 Янв '16 15:58) falcao

@plitka: у меня есть некий план, как свести эту задачу к предыдущей, в которой разрешалось использовать при построении NOT и XOR. Но надо продумать ответ, чтобы было не очень длинно.

(27 Янв '16 15:59) falcao
10|600 символов нужно символов осталось
0

Реализуем функцию MAJ в виде той схемы, которая основана на использовании xor и отрицаний. Она была описана здесь. Далее xor выражается в виде $%a+b=\bar{a}b\lor a\bar{b}$%. Получается схема полиномиального размера из конъюнкций, дизъюнкций и отрицаний. Применяя законы де Моргана, преобразуем схему к такому виду, где отрицания навешиваются только на входные переменные. Число элементов $%\land$% и $%\lor$% при этом не меняется.

Мы в итоге получим монотонную схему полиномиального размера от $%x_1,...,x_n$% и $%y_1,...,y_n$%, где $%y_i=\bar{x}_i$% для $%1\le i\le n$%. Утверждается, что функция будет принимать те же значения на любых наборах, если все $%y_i$% заменить единицами (и далее упростить по законам поглощения). Тогда получится монотонная схема полиномиального размера для вычисления MAJ.

Представим себе, что мы вместо $%y_i=\bar{x_i}$% поставили $%1$% при некотором $%i$%. Тогда, если $%x_i=0$%, то на таком наборе значение функции не изменилось. Пусть $%x_i=1$%. Предположим, что значение изменилось. Схема от переменных $%x_1,...,x_n$% и $%y_1,...,y_n$% у нас монотонна, поэтому увеличение значений переменных с $%y_i$% на 1 могло привести только к увеличению значения функции, задаваемой схемой. Тогда получается, что при $%x_i=1$% наша схема даёт 0, а при $%x_i=0$%, когда $%y_i$% становится равной 1, схема даёт 1. Но это противоречит монотонности функции MAJ, задаваемой нашей схемой.

ссылка

отвечен 28 Янв '16 15:25

@falcao Допустим, при x_i = 0 MAJ принимает значение 0, при x_i = 1 тоже, а при изменении потом y_i с 0 на 1 значение функции становится 1. Вроде бы это не нарушает монотонность схемы и не нарушает мнотонность MAJ. Не понимаю, в каком месте вашего решения наступает противоречие с этим примером. Спасибо!

(4 Мар 23:20) podol

@alisterOrange: если при x(i)=0 значение MAJ равно 0, то на наборе с x(i)=0, y(i)=not(x(i))=1 функция от "иксов" и "игреков" должна выдать настоящее значение MAJ, то есть 0. А в Вашем примере она выдаёт 1. Противоречие возникает с тем фактом, что нами была создана функция от x(i), not(x(i)), выдающее значение функции MAJ.

(5 Мар 4:28) falcao
1

@falcao нет, я говорю именно про случай, когда при x(i)=0 наша схема выдает верный ответ, то есть 0, а вот при x(i)=1, когда y(i)=0, если верный ответ равен все еще 0, а наша схема начала давать 1 из-за замены y(i) на 1. Мы же как раз пытаемся прийти к противоречию с тем, что функция выдала ошибку, но в таком случае монотонность не нарушена.

(5 Мар 9:38) podol

@alisterOrange: я перечитал в очередной раз концовку своего рассуждения. Судя по всему, там действительно есть дефект. Я не знаю пока, можно ли эту конструкцию как-то "спасти". Над задачей думал уже давно, детали сейчас подзабыл.

(6 Мар 1:57) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×148

задан
27 Янв '16 1:36

показан
1806 раз

обновлен
7 Мар 14:57

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

по почте:

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

по RSS:

Ответы

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

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