Твердость шумных булевых функций

13

Пусть - булева функция от n булевых переменных. Пусть g ( x ) = T ϵ ( f ) ( x ) будет ожидаемым значением f ( y ), когда y получается из x путем переключения каждой координаты с вероятностью ϵ / 2 .fng(x)=Tϵ(f)(x)f(y)yxϵ/2

Меня интересуют случаи, когда в вычислительном отношении трудно приблизить . Позвольте мне зафиксировать понятие «приближения» (но могут быть и другие): булева функция h приближает g, если h ( x ) = 1, когда g ( x ) 0,9, и h ( x ) = 0, когда g ( x ) 0,1ghgh(x)=1g(x)0.9h(x)=0g(x)0.1. Счетный аргумент (основанный на существовании положительных кодов, исправляющих ошибки скорости), по-видимому, указывает на наличие булевых функций, для которых любое такое приближение требует схемы экспоненциального размера. Но вопрос в том, что происходит, когда для начала находится в NP или в его окрестности.f

Q1: Есть ли пример того, как описывается схемой NP (или P-пространством), так что каждый h является NP трудным или жестким в некотором более слабом смысле.fh

Чтобы увидеть это h не всегда может быть легко (я благодарю Джоен Хастад за полезное обсуждение о нем) можно рассматривать свойство графов , имеющую клику размера , для случайного ввода, можно предположить , что это трудно Определите, есть ли большая клика, но это проявляется в том, что на графике с шумом больше, чем ожидалось, клики размера log n. В этом случае любой h будет, вероятно, жестким (но не доказуемо и не ужасно сложным, как говорят квазиполиномиальные схемы).n1/4h

Q2: Какова ситуация, если для начала низкая сложность. ( A C 0 , монотонный T C 0 , A C C и т. Д.)fAC0TC0ACC

Q3: Как обстоят дела с некоторыми основными примерами булевых функций? (Вопрос может быть распространен и на вещественную функцию.)

Q4: Можно ли задать вышеупомянутый вопрос формально для единой модели вычислений (машины Тьюринга)?

Обновление: учитывая ответ Энди (Привет, Энди), я думаю, что самый интересный вопрос - понять ситуацию для различных конкретных функций.

Обновление Еще один вопрос Q5 [Q1 для монотонных функций] (также с учетом ответа Энди). Какова ситуация, если является монотонным? Можем ли мы все еще надежно закодировать NP завершенные вопросы>f

Гил Калай
источник
Имхо этот вопрос о приближении схемы связан. Ваш вопрос, похоже, похож на вопрос P / poly vs NP.
2013 года

Ответы:

14

на вопрос 1 ответ - да, и его можно показать следующим образом. (Я также буду неявно набрасывать утвердительный ответ на вопрос 4, так как аргумент является равномерным и будет обрабатывать все входные длины сразу.)

Исправьте любой NP-полный язык и семейство хороших двоичных кодов, исправляющих ошибки (например, со скоростью 1/4 и исправлением из доли ошибок .1). Пусть E n c n : { 0 , 1 } n{ 0 , 1 } 4 n - функция кодирования для длины n ; мы используем некоторый такой код, где E n c = { E n c n } вычисляется с помощью равномерного алгоритма полиномиального времени.LEncn:{0,1}n{0,1}4nnEnc={Encn}

Определите как набор строк z, которые находятся на расстоянии не более .05 | z | от кодового слова у Е н гр ( L ) , кодирующий некоторый элемент L . Заметим , что L ' в НП, как вы можете догадаться и проверить близлежащий кодовое слово, декодированного слово и сертификат NP для членства декодированной слово в L . Lz.05|z|yEnc(L)LLL

Тогда утверждается, что любое «приближение» в вашем смысле является NP-трудным для ε = .01 . Поскольку, если мы рассмотрим действительное кодовое слово y = E n c ( x ) некоторой длины 4 n , то с вероятностью 1 - o ( 1 ) по случайной ε- возмущенной версии y of y оно будет не соответствовать y в не более чем .05 фракция координат, и поэтому будет не согласен с любым другим кодовым словом E n cLε=.01y=Enc(x)4n1o(1)εyyy в более чем 0,05 доли координат. Для такого у ' мы имеем у 'L ' тогдатолько тогда х L . Таким образом, если h - любое приближение к ε -сглаженной версии L в вашем смысле, то мы должны иметь h ( y ) = L ( x ) . Поскольку E n c является эффективно вычисляемым, это дает нам возможность эффективно свести вопросы членства для L к вопросам для h . ТакEncn.05yyLxLhεLh(y)=L(x)EncLh NP-сложный.h

Две заметки:

(1) исправляющие ошибки кодировки экземпляров NP использовались ранее в нескольких статьях, в частности
Д. Сивакумар: О сопоставимых наборах членства. J. Comput. Сист. Sci. 59 (2): 270-280 (1999).

(2) рассмотренный выше аргумент, конечно, ничего не говорит о сложности среднего случая любой проблемы NP, поскольку исправление ошибок применяется в каждом конкретном случае.

Энди Друкер
источник
8
Программное обеспечение не позволит мне начать свой ответ с «Привет, Гил», и меня немного пугает этот уровень микроуправления.
Энди Друкер
2
Это потому, что ваш ответ не должен начинаться с "Привет, Гил". Это не личное письмо, это сообщение на общедоступном веб-сайте. Конечно, такие как вы не те, на кого нацелены; это довольно новые пользователи, которые не знают об этих соглашениях, которыми программное обеспечение стремится управлять.
Юваль Фильмус
1
Я считаю, что хорошо осознавать, когда кто-то пишет в ответ на чей-либо вклад. Это нормально и положительно во многих онлайн-настройках. Я попытался сделать это в кратчайшие сроки, по личному адресу; не вижу в этом ничего плохого.
Энди Друкер
2
Хорошая конструкция! У меня есть вопрос: пусть f будет индикаторной функцией L ', а h будет таким же, как в вопросе Гила. Теперь ваш аргумент показывает, что h согласуется с f на y, которые являются допустимыми кодовыми словами. Но как насчет y, которые не являются законными кодовыми словами?
Или Меир
2
f