Пусть - булева функция от n булевых переменных. Пусть g ( x ) = T ϵ ( f ) ( x ) будет ожидаемым значением f ( y ), когда y получается из x путем переключения каждой координаты с вероятностью ϵ / 2 .
Меня интересуют случаи, когда в вычислительном отношении трудно приблизить . Позвольте мне зафиксировать понятие «приближения» (но могут быть и другие): булева функция h приближает g, если h ( x ) = 1, когда g ( x ) ≥ 0,9, и h ( x ) = 0, когда g ( x ) ≤ 0,1. Счетный аргумент (основанный на существовании положительных кодов, исправляющих ошибки скорости), по-видимому, указывает на наличие булевых функций, для которых любое такое приближение требует схемы экспоненциального размера. Но вопрос в том, что происходит, когда для начала находится в NP или в его окрестности.
Q1: Есть ли пример того, как описывается схемой NP (или P-пространством), так что каждый h является NP трудным или жестким в некотором более слабом смысле.
Чтобы увидеть это не всегда может быть легко (я благодарю Джоен Хастад за полезное обсуждение о нем) можно рассматривать свойство графов , имеющую клику размера , для случайного ввода, можно предположить , что это трудно Определите, есть ли большая клика, но это проявляется в том, что на графике с шумом больше, чем ожидалось, клики размера log n. В этом случае любой h будет, вероятно, жестким (но не доказуемо и не ужасно сложным, как говорят квазиполиномиальные схемы).
Q2: Какова ситуация, если для начала низкая сложность. ( A C 0 , монотонный T C 0 , A C C и т. Д.)
Q3: Как обстоят дела с некоторыми основными примерами булевых функций? (Вопрос может быть распространен и на вещественную функцию.)
Q4: Можно ли задать вышеупомянутый вопрос формально для единой модели вычислений (машины Тьюринга)?
Обновление: учитывая ответ Энди (Привет, Энди), я думаю, что самый интересный вопрос - понять ситуацию для различных конкретных функций.
Обновление Еще один вопрос Q5 [Q1 для монотонных функций] (также с учетом ответа Энди). Какова ситуация, если является монотонным? Можем ли мы все еще надежно закодировать NP завершенные вопросы>
Ответы:
на вопрос 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 } вычисляется с помощью равномерного алгоритма полиномиального времени.L Encn:{0,1}n→{0,1}4n n Enc={Encn}
Определите как набор строк z, которые находятся на расстоянии не более .05 | z | от кодового слова у ∈ Е н гр ( L ) , кодирующий некоторый элемент L . Заметим , что L ' в НП, как вы можете догадаться и проверить близлежащий кодовое слово, декодированного слово и сертификат NP для членства декодированной слово в L .L′ z .05|z| y∈Enc(L) L L′ L
Тогда утверждается, что любое «приближение» в вашем смысле является NP-трудным для ε = .01 . Поскольку, если мы рассмотрим действительное кодовое слово y = E n c ( x ) некоторой длины 4 n , то с вероятностью 1 - o ( 1 ) по случайной ε- возмущенной версии y ′ of y оно будет не соответствовать y в не более чем .05 фракция координат, и поэтому будет не согласен с любым другим кодовым словом E n cL′ ε=.01 y=Enc(x) 4n 1−o(1) ε y′ y y в более чем 0,05 доли координат. Для такого у ' мы имеем у ' ∈ L ' тогдатолько тогда х ∈ L . Таким образом, если h - любое приближение к ε -сглаженной версии L ′ в вашем смысле, то мы должны иметь h ( y ) = L ( x ) . Поскольку E n c является эффективно вычисляемым, это дает нам возможность эффективно свести вопросы членства для L к вопросам для h . ТакEncn .05 y′ y′∈L′ x∈L h ε L′ h(y)=L(x) Enc L h NP-сложный.h
Две заметки:
(1) исправляющие ошибки кодировки экземпляров NP использовались ранее в нескольких статьях, в частности
Д. Сивакумар: О сопоставимых наборах членства. J. Comput. Сист. Sci. 59 (2): 270-280 (1999).
(2) рассмотренный выше аргумент, конечно, ничего не говорит о сложности среднего случая любой проблемы NP, поскольку исправление ошибок применяется в каждом конкретном случае.
источник