Przybliżenie problemów trudnych do # P

9

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?

— użytkownik0928
źródło

Gdyby

k = 2^{n - 1} - p o l y (n)

$k=2^{n-1}-\mathrm{poly}(n)$ istnieje algorytm wieloczasowy z błędem addytywnym

k

$k$ . Gdyby

k = 2^{n} / p o l y (n)

$k=2^{n}/\mathrm{poly}(n)$ , wówczas istniałby losowy algorytm wieloczasowy z błędem addytywnym

k

$k$ . Kiedy

k

$k$ jest znacznie mniejszy (ale nie wielomianowo mały), oczekiwałbym, że będzie twardy NP, ale nie twardy # P, ponieważ twardość #P zwykle zależy od dokładnego obliczenia.

— Thomas

Czy możesz podać odniesienie dla pierwszych dwóch roszczeń? Przepraszam, jestem początkującym ...

— użytkownik0928

10

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} α - a | = 2^{n} | α - a / 2^{n} |,

$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$ co jest równoważne z

| α - a / 2^{n} | \leq ε .

$|\alpha - a/2^n| \leq \varepsilon.$ Przez nierówność chernoffa ,

P [| α - a / 2^{n} | > ε] \leq 2^{- Ω (m ε^{2})},

$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$ tak jak

E [ϕ (X_{i})] = E [α] = a / 2^{n}

$\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$ . Oznacza to, że jeśli zdecydujemy

m = O (1 / ε^{2}) = p o l y (n)

$m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (i zapewnić

m

$m$ jest mocą

2

$2$ ), przynajmniej z prawdopodobieństwem

0.99

$0.99$ błąd jest co najwyżej

k

$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} | = | \frac{a - \hat{a}}{2^{n - m}} | \leq \frac{k}{2^{n - m}} < 1 / 2.

$|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

$b$ jest liczbą całkowitą, co oznacza, że możemy określić dokładną wartość

b

$b$ od

\hat{a}

$\hat{a}$ . Algorytmiczne określenie dokładnej wartości

b

$b$ wymaga rozwiązania problemu # P-zupełnego # 3SAT. Oznacza to, że trudno jest obliczyć #P

\hat{a}

$\hat{a}$ .

— Tomasz
źródło

4

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

— Martin Schwarz
źródło