Вычисление любой информации о Max-3SAT

Для формулы 3CNF пусть будет максимальное число удовлетворенных положений в любом присвоении . Известно, что Max-3SAT трудно аппроксимировать (при условии P ≠ NP), то есть не существует алгоритма множителя, вход которого является формулой 3CNF , а выход которого равен числу , так что находится в пределах мультипликативный фактор из , где - абсолютная положительная постоянная.$C$$M(C)$$C$$C$$M'$$M(C)$$1+c$$M'$$c>0$

Я считаю, что NP-сложнее вычислить для любого постоянного модуля p . Интересно, верно ли следующее общее обобщение этих двух фактов: не существует многочастичного алгоритма, чьи входные данные представляют собой 3CNF-формулу C с N предложениями и строкой \ log_2 NB вспомогательных битов и чьи выходные данные равны M (C) . Здесь B - абсолютная постоянная. Проще говоря, не существует алгоритма, который вычисляет B битов информации M (C) .$M(C) \bmod p$C N log 2 N - B M ( C ) B B M ( C $p$$C$$N$$\log_2 N-B$$M(C)$$B$$B$$M(C)$

Я прошу прощения, если у вопроса есть известный ответ, поскольку я не теоретик сложности с точки зрения фона.

Вот аргумент, что если бы вы могли решить Max 3SAT на экземпляре m-предложения, учитывая постоянное число советов, то иерархия полиномов рухнула бы.

Исправьте NP-полную задачу L. Из теоремы Кука мы знаем преобразование f () входов x для L в формулы 3SAT f (x), так что

1) если тоM ( f ( x ) ) = $x\in L$$M(f(x)) = m$

2) если тоM ( f ( x ) ) = m - $x\in L$$M(f(x)) = m-1$

где - количество предложений в .ф ( х $m$$f(x)$

У нас также есть теорема Кадина, которая гласит, что если задано входов NP-полной задачи, у вас есть алгоритм за полиномиальное время, который делает запросов к оракулу NP и определяет правильный ответ на проблемам NP , то полиномиальная иерархия разрушается.x 1 , … , x k ≤ k - 1 k x i ∈ ? $k$$x_1,\ldots,x_k$$\leq k-1$$k$$x_i \in ? L$

Предположим, у нас есть алгоритм, который решает Max SAT на входах m-предложения с учетом k советов. Мы будем использовать результат Хастада для построения алгоритма, как в предположении теоремы Кадина.

Начать с входы к задаче . Примените теорему Кука к каждому из них. После некоторой нормализации (которая может быть сделана путем присвоения весов предложениям или дублирования их, если мы не хотим использовать весы), мы создаем формул где для определенного :x 1 , … , x K L K F 1 , … , F K$K=2^k+1$$x_1,\ldots,x_K$$L$$K$$F_1,\ldots,F_K$$m$

1) если и противном случаеx 1 ∈ L M ( F 1 ) = m - $M(F_1)= m-1$$x_1 \in L$$M(F_1) = m-2$

2) если и противном случаеx 2 ∈ L M ( F 2 ) = m ⋅ ( m - 2 $M(F_2) = m\cdot (m-1)$$x_2 \in L$$M(F_2) = m\cdot (m-2)$

...

k) если и противном случаеx K ∈ L M ( F K ) = m K - 1 ⋅ ( m - 2 $M(F_K) = m^{K-1} \cdot (m-1)$$x_K\in L$$M(F_K) = m^{K-1} \cdot (m-2)$

Теперь возьмем объединение формул, которые были построены более непересекающихся множеств переменных, и назвать его . Таким образом, мы имеем , и мы можем «зачитать» ответ на задач , посмотрев на базовое представление . Если мы можем вычислить учетом советов, это означает, что мы можем найти значений, таких что . Затем мы можем неадекватно спросить оракула NP, является ли для каждого из значений-кандидатовM ( F ) = M ( F 1 ) + ⋯ + M ( F k ) K x i ∈ ? L m M ( F ) M $F$$M(F) = M(F_1) + \cdots + M(F_k)$$K$$x_i \in? L$$m$$M(F)$k 2 k M ( F ) M ( F ) ≥ n i n 1 , … , n 2 k 2 k + 1 $M(F)$$k$$2^k$$M(F)$$M(F) \geq n_i$$n_1,\ldots,n_{2^k}$мы создали. Таким образом, мы смогли решить экземпляров NP-полных задач, сделав неадаптивных запросов к NP oracle, что подразумевает коллапс полиномиальной иерархии.$2^k+1$$2^k$

Используя теорему Хастада вместо теоремы Кука, можно увеличить размер до вместо , поэтому можно нажать в и количество битов подсказок в . Понять, что происходит, когда вам дают советы, кажется действительно трудным.$F$m k k log m log log m log m - O ( 1 $O(1)^k \cdot m$$m^k$$k$$\log m$$\log\log m$$\log m - O(1)$

Отредактировано, чтобы добавить: Крентел ( Сложность задач оптимизации . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) доказал, что вычисление значения оптимума задачи максимальной клики завершено для , класс функций, вычислимых за полиномиальное время с запросов к оракулу NP. Полнота находится в разделе «Сокращение одного запроса», в котором функция f сводится к функции g, если можно записать для вычислимых за полиномиальное время и . Предположительно, то же самое верно для Max Clique. Теперь, если Max Clique имел алгоритм полиномиального времени, который производит список O ( l o g n ) f ( x ) = r 1$FP^{NP[O(log n)]}$$O(log n)$r 1 r 2 m o ( 1 ) F P N P [ o ( l o g n ) $f(x) = r_1(g(r_2(x))$$r_1$$r_2$$m^{o(1)}$возможные значения, это будет в , потому что вы можете использовать бинарный поиск, чтобы найти оптимальное число запросов, которое является журналом размера списка.$FP^{NP[o(logn)]}$

Теперь, если у нас есть мы определенно имеем , который является особым случаем для решения проблем, и который известен по результатам Вагнера (улучшение результата Кадина, который применяется к постоянному количеству запросов), чтобы свернуть иерархию полиномов. Но я думаю, что может быть известно, что фактически подразумевает P = NP. Но в любом случае результатов Крентеля и Кадин-Вагнера должно быть достаточно, чтобы дать еще одно доказательство результата Энди Друкера. Теперь мне интересно, если это на самом деле то же самое доказательство, то есть, если результат Fortnow-Van Melkebeek работает, явно или неявно, через аргумент «имитация запросов NP с меньшим количеством запросов NP». P N P [ O ( l o g n ) ] = P N P [ o ( l o g n ) ] F P N P [ O ( l $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$$P^{NP[O(log n)]} = P^{NP[o(log n)]}$$FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$

Хороший обзорный документ, который объясняет, что происходит с проблемами оптимизации и ограниченными классами запросов:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Я хотел бы указать одну причину, по которой трудно доказать NP-сложность этой проблемы.

В комментарии к вопросу Лука Тревизан дал хороший способ переформулировать проблему: разрешима ли следующая задача за полиномиальное время для каждой константы k ? Учитывая формулу CNF C с m предложениями, выведите не более m / k целых чисел, чтобы одно из них было равно M ( C ). Здесь к связано с B по K = 2 ^B .

Тем не менее, давайте потребовать больше. А именно, мы рассмотрим следующую проблему: с учетом формулы C CNF выведите два целых числа, чтобы одно из них было равно M ( C ). Обозначим эту проблему через Π. Задача Π, по крайней мере, такая же сложная, как и исходная проблема, поэтому, если исходная проблема является NP-трудной, also также должна быть NP-трудной.

Обратите внимание, что Π является проблемой отношений. Одним из простейших видов редукций, который можно использовать для сведения некоторой проблемы L к проблеме отношений Π, является редукция Левина за полиномиальное время, которая является частным случаем редуцирования Тьюринга за полиномиальное время, когда редукция вызывает оракула только для Π один раз.

Покажем, что P ^{Π [1]} = P. Это, очевидно, подразумевает, что NP⊈P ^{1 [1],} если P = NP, то есть Π не является NP-трудной при сводимости Левина за полиномиальное время, если P = NP.

Доказательство . Пусть L ∈P ^{Π [1]} или, другими словами, существует редукция Левина от L к Π. Это означает, что существует пара ( f , g ) вычислимой функции f за полиномиальное время : {0,1} ^* → {0,1} ^*, которая отображает каждый экземпляр x задачи L в некоторую формулу CNF f ( x) ) и вычислимый предикат полиномиального времени g : {0,1} ^* × ℕ × ℕ → {0,1} такой, что g ( x , i , j ) = L( x ) если i или j равен M ( f ( x )). (Здесь L ( x ) = 1, если x является экземпляром L для yes, и L ( x ) = 0, если x является экземпляром no.)

Из этого мы построим алгоритм полиномиального времени для L следующим образом. Пусть х будет входом.

1. Пусть C = ф ( х ), и пусть т быть числом положений в C .
2. Найдите один i ∈ {0,…, m } такой, что значение g ( x , i , j ) постоянно и не зависит от j ∈ {0,…, m }.
3. Выведите эту константу g ( x , i , 0).

На шаге 2 такой i всегда существует, потому что i = M ( f ( x )) удовлетворяет условию. Более того, этот алгоритм не может вывести неправильный ответ, потому что g ( x , i , M ( f ( x ))) должен быть правильным ответом. Следовательно, этот алгоритм решает L правильно. КЕД .

Если я не ошибаюсь, эту же идею можно использовать для доказательства того, что P ^{Π [ k ( n )]} TDTIME [ n ^{O ( k ( n ))} ]. Это означает, что NP⊈P ^{Π [ k ]} для любой постоянной k, если P = NP, и что NP andP ^{Π [polylog],} если NP⊆DTIME [2 ^polylog ]. Однако сама по себе эта идея, по-видимому, не исключает возможности того, что NP является NP-трудным при сводимости Тьюринга за полиномиальное время.

Я считаю, что мы можем показать:

Запрос. Существует значение такое, что верно следующее. Предположим, что существует детерминированный многополосный алгоритм, который, учитывая пункт 3-SAT instance , выводит список не более чем из значений, таких что ; тогда иерархия полиномов разрушается.m ϕ S m c M ( ϕ ) ∈ $0 < c < 1$$m$$\phi$$S$$m^c$$M(\phi) \in S$

В доказательстве использованы результаты Fortnow и Santhanam о невозможности сжатия экземпляров из их статьи http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

В частности, глядя на их доказательство Thm 3.1, я считаю, что можно извлечь следующее (я проверю это в ближайшее время):

«Теорема» [ФС]. Существуют целые числа , так что верно следующее. Предположим, что в детерминированном поли-времени можно преобразовать ИЛИ из булевых формул (каждая из длины и на непересекающихся наборах переменных) в ИЛИ из формул (снова переменная-дизъюнкт и длины ), сохраняя выполнимость / неудовлетворенность OR. Тогда и иерархия полиномов разрушается.$0 < d' < d$$n^d$$\leq n$$n^{d'}$$\leq n$$\mathsf{NP} \subseteq \mathsf{coNP/poly}$

Доказательством нашего утверждения будет сокращение задачи OR-сжатия, упомянутой в приведенной выше теореме [FS], до задачи вычисления списка . Предположим, что - это список формул, чье ИЛИ мы хотим сжать.$M(\phi)$$\psi_1, \ldots, \psi_{n^d}$

Первый шаг: определите схему полиномиального размера для входных строк . Здесь строка кодирует присвоение , а кодирует число от до .$\Gamma$$(v, y_1, \ldots, y_{n^d})$$y_i$$\psi_i$$v \in \{0, 1\}^{d \log n + 1}$$0$$n^d$

Мы принимаем если либо , либо .$\Gamma$$v = 0$$\psi_v(y_v) = 1$

Теперь пусть обозначает максимальное значение , такое что ограниченная схема выполнима. (Это количество всегда не менее 0).$M^*(\Gamma)$$v$$\Gamma(v, \cdot, \ldots, \cdot)$

Предположим, что мы можем эффективно создать список возможных значений для . Тогда утверждается, что в нашем списке мы можем выбросить все для которых ; результирующий список содержит выполнимую формулу, если исходный. Я надеюсь, что это ясно из проверки.$S$$M^*(\Gamma)$$\psi_1, \ldots, \psi_{n^d}$$\psi_i$$i \notin S$

Вывод: мы не можем надежно создать список из возможных значений для , если иерархия поли не разрушится.$S$$\leq n^{d'}$$M^*(\Gamma)$

Второй шаг: мы сводим задачу вычисления списков к проблеме вычислений списков для экземпляров 3-SAT .$M^*(\Gamma)$$M(\phi)$$\phi$

Для этого мы сначала запускаем редукцию Кука на чтобы получить экземпляр 3-SAT размером . имеет тот же набор переменных, что и , вместе с некоторыми вспомогательными переменными. Наиболее важно для наших целей, выполнимо тогда и только тогда, когда выполнимо.$\Gamma$$\phi_1$$m = poly(n^d)$$\phi_1$$\Gamma$$\phi_1(v, \cdot)$$\Gamma(v, \cdot)$

Мы называем "сильными ограничениями". Мы даем каждому из этих ограничений вес (добавляя дублирующие ограничения). 2 $\phi_1$$2m$

Затем мы добавляем набор «слабых ограничений» который добавляет предпочтение тому, чтобы индекс (определенный на шаге 1) был как можно выше. Для каждого бита из существует одно ограничение , а именно . Мы позволили му наиболее значимому биту иметь ограничение веса . Поскольку имеет длину , эти веса можно сделать интегральными (нам просто нужно дополнить, чтобы было степенью 2). v v t v [ v t = 1 ] t v m / 2 t - $\phi_2$$v$$v_t$$v$$[v_t = 1]$$t$$v$$m/2^{t-1}$d log n + 1 $v$$d \log n + 1$$m$

Наконец, пусть будет выводом нашей редукции.$\phi = \phi_1 \wedge \phi_2$

Чтобы проанализировать , пусть - набор переменных , с как и раньше. Прежде всего обратите внимание, что при любом назначении можно вывести значение из величины (общий вес ограничений, удовлетворяемых ). Это следует из иерархического дизайна весов ограничений (аналогично методике из ответа Луки). Точно так же максимально достижимое значение достигается установкой которая удовлетворяет всем строгим ограничениям, и где (при условии)( v , z ) ϕ v ( v , z ) v N ( v , z ) = ϕ v , z M ( ϕ ) $\phi$$(v,z)$$\phi$$v$$(v, z)$$v$$N(v, z) =$$\phi$$v, z$
$M(\phi)$$(v, z)$$v$настолько велика, насколько это возможно. Это самый большой индекс, для которого выполнимо , а именно . (Обратите внимание, что, установив all-0, всегда можно удовлетворить все строгие ограничения, поскольку в этом случае выполнимо.)$v$$\Gamma(v, \cdot)$$M^*(\Gamma)$$v =$$\Gamma(v, \cdot)$

Отсюда следует, что, если нам дан список возможных значений , мы можем получить списоквозможные значения . Таким образом, мы не можем иметь если иерархия поли не рухнет. Это дает Требование, так как .M ( ϕ ) | S | M ∗ ( Γ ) | S | ≤ n d ′ n d ′ = m Ω ( 1 $S$$M(\phi)$$|S|$$M^*(\Gamma)$$|S| \leq n^{d'}$$n^{d'} = m^{\Omega(1)}$