Przybliżenie problemów trudnych do # P

Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z $n$zmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia$2^{n-1}$- błąd, ale jeśli $k<2^{n-1}$, czy można mieć skuteczny algorytm aproksymacyjny, czy ten problem jest również trudny do rozwiązania?

Interesują nas przybliżone dodatki do # 3SAT. tzn. biorąc pod uwagę 3CNF$\phi$ na $n$ zmienne liczą liczbę spełniających przypisań (nazwij to $a$) aż do błędu addytywnego $k$.

Oto kilka podstawowych wyników:

Przypadek 1: $k=2^{n-1}-\mathrm{poly}(n)$

Oto deterministyczny algorytm wieloczasowy: Let $m=2^n-2k = \mathrm{poly}(n)$. Teraz oceń$\phi$ na $m$ dowolne dane wejściowe (np. najpierw leksykograficznie $m$wejścia). Przypuszczać$\ell$ z tych danych wejściowych spełniają $\phi$. Więc wiemy$a \geq \ell$ jak są przynajmniej $\ell$ spełnianie zadań i $a \leq 2^n - (m-\ell)$ jak są przynajmniej $m-\ell$niezadowalające zadania. Długość tego przedziału wynosi$2^n - (m-\ell) - \ell = 2k$. Więc jeśli wyprowadzimy punkt środkowy$2^{n-1} -m/2 + \ell$ to jest w środku $k$ poprawnej odpowiedzi, zgodnie z wymaganiami.

Przypadek 2: $k=2^n/\mathrm{poly}(n)$

Tutaj mamy losowy algorytm wieloczasowy: Oceń $\phi$ w $m$ losowe punkty $X_1, \cdots, X_m \in \{0,1\}^n$. Pozwolić$\alpha = \frac{1}{m} \sum_{i=1}^m \phi(X_i)$ i $\varepsilon = k/2^n$. Produkujemy$2^n \cdot \alpha$. Aby miał to co najwyżej błąd$k$ potrzebujemy

$$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ co jest równoważne z $|\alpha - a/2^n| \leq \varepsilon.$Przez nierówność chernoffa , $$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ tak jak $\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$. Oznacza to, że jeśli zdecydujemy$m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (i zapewnić $m$ jest mocą $2$), przynajmniej z prawdopodobieństwem $0.99$błąd jest co najwyżej $k$.

Przypadek 3: $k=2^{cn + o(n)}$ dla $c < 1$

W tym przypadku problemem jest # P-trudny: Zrobimy redukcję z # 3SAT. Weź 3CNF$\psi$ na $m$zmienne. Wybierać$n \geq m$ takie, że $k < 2^{n-m-1}$ -- to wymaga $n = O(m/(1-c))$. Pozwolić$\phi=\psi$ z wyjątkiem $\phi$ jest teraz włączony $n$ zmienne zamiast $m$. Gdyby$\psi$ ma $b$ spełnianie zadań $\phi$ ma $b \cdot 2^{n-m}$ spełniające zadania, jak $n-m$„wolne” zmienne mogą przyjmować dowolne wartości w zadowalającym przypisaniu. Załóżmy teraz, że mamy$\hat{a}$ takie, że $|\hat{a}-a| \leq k$ -- to jest $\hat{a}$ jest przybliżeniem liczby spełniających zadania zadań $\phi$ z błędem addytywnym $k$. Następnie

$$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} < 1/2.$$ Od $b$ jest liczbą całkowitą, co oznacza, że ​​możemy określić dokładną wartość $b$ od $\hat{a}$. Algorytmiczne określenie dokładnej wartości$b$wymaga rozwiązania problemu # P-zupełnego # 3SAT. Oznacza to, że trudno jest obliczyć #P$\hat{a}$.

Oto odniesienie do Bordewich, Freedman, Lovász i Welsh, którzy do pewnego stopnia rozwijają ten temat.