Аппроксимация # P-сложные проблемы

Рассмотрим классическую # P-полную задачу # 3SAT, т. Е. Посчитаем количество оценок, чтобы сделать 3CNF с переменными выполнимыми. Меня интересует аддитивная аппроксимируемость. Ясно, что существует тривиальный алгоритм для достижения -ошибки, но если , возможно ли иметь эффективный алгоритм аппроксимации, или эта проблема также является # P-трудной ?$n$$2^{n-1}$$k<2^{n-1}$

Нас интересуют аддитивные приближения к # 3SAT. т.е. дан 3CNF$\phi$ на $n$ переменные подсчитывают количество удовлетворяющих заданий $a$) до аддитивной ошибки $k$,

Вот некоторые основные результаты для этого:

Дело 1: $k=2^{n-1}-\mathrm{poly}(n)$

Здесь есть детерминированный многовременный алгоритм: Пусть $m=2^n-2k = \mathrm{poly}(n)$, Сейчас оцените$\phi$ на $m$ произвольные входные данные (например, лексикографически первый $m$входы). предполагать$\ell$ из этих входов удовлетворяют $\phi$, Тогда мы знаем$a \geq \ell$ как минимум $\ell$ удовлетворяющие задания и $a \leq 2^n - (m-\ell)$ как минимум $m-\ell$неудовлетворительные задания. Длина этого интервала$2^n - (m-\ell) - \ell = 2k$, Так что, если мы выведем среднюю точку$2^{n-1} -m/2 + \ell$ это внутри $k$ правильного ответа, как требуется.

Случай 2: $k=2^n/\mathrm{poly}(n)$

Здесь у нас есть рандомизированный алгоритм поли-времени: Оценить $\phi$ в $m$ случайные точки $X_1, \cdots, X_m \in \{0,1\}^n$, Позволять$\alpha = \frac{1}{m} \sum_{i=1}^m \phi(X_i)$ а также $\varepsilon = k/2^n$, Мы выводим$2^n \cdot \alpha$, Для того, чтобы это было не более$k$ нам нужно

$$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ что эквивалентно $|\alpha - a/2^n| \leq \varepsilon.$По Чернову связаны , $$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ в виде $\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$, Это подразумевает, что если мы выберем$m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (и обеспечить $m$ это сила $2$), то с вероятностью не менее $0.99$ошибка не более $k$,

Случай 3: $k=2^{cn + o(n)}$ за $c < 1$

В этом случае проблема # P-hard: мы сделаем сокращение от # 3SAT. Возьми 3CNF$\psi$ на $m$переменные. Выбирать$n \geq m$ такой, что $k < 2^{n-m-1}$ -- это требует $n = O(m/(1-c))$, Позволять$\phi=\psi$ Кроме $\phi$ сейчас на $n$ переменные, а не $m$, Если$\psi$ имеет $b$ выполняя задания, то $\phi$ имеет $b \cdot 2^{n-m}$ удовлетворяющих заданий, как $n-m$«Свободные» переменные могут принимать любое значение в удовлетворительном присваивании. Теперь предположим, что у нас есть$\hat{a}$ такой, что $|\hat{a}-a| \leq k$ -- это $\hat{a}$ является приближением к числу удовлетворяющих заданий $\phi$ с аддитивной ошибкой $k$, затем

$$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} < 1/2.$$ поскольку $b$ является целым числом, это означает, что мы можем определить точное значение $b$ от $\hat{a}$, Алгоритмическое определение точного значения$b$влечет за собой решение # P-полной задачи # 3SAT. Это означает, что это # ​​P-трудно вычислить$\hat{a}$,

Вот ссылка на Bordewich, Freedman, Lovász и Welsh, которая развивает эту тему в некоторой степени.