Approximation des problèmes # P-hard

Considérons le problème classique # P-complet # 3SAT, c'est-à-dire de compter le nombre d'évaluations pour rendre un 3CNF avec variables satisfaisable. Je m'intéresse à l' approximabilité additive . De toute évidence, il existe un algorithme trivial pour obtenir une erreur de , mais si , est-il possible d'avoir un algorithme d'approximation efficace, ou ce problème est également # P-difficile ?$n$$2^{n-1}$$k<2^{n-1}$

Nous sommes intéressés par les approximations additives de # 3SAT. c'est-à-dire, étant donné un 3CNF sur variables, comptez le nombre d'affectations satisfaisantes (appelez ceci ) jusqu'à l'erreur additive .n a $\phi$$n$$a$$k$

Voici quelques résultats de base pour cela:

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

Ici, il existe un algorithme de temps poly déterministe: Soit . Maintenant, évaluez sur entrées arbitraires (par exemple, les premières entrées lexicographiquement ). Supposons que de ces entrées satisfasse . On connaît alors car il y a au moins assignations satisfaisantes et car il y a au moins assignations insatisfaisantes. La longueur de cet intervalle est de . Donc, si nous sortons le point milieu cela se trouve dansϕ m m ℓ ϕ a ≥ ℓ ℓ a ≤ 2 n - ( m - ℓ ) m - ℓ 2 n - ( m - ℓ ) - ℓ = 2 k 2 n - 1 - m / 2 + ℓ $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$ de la bonne réponse, au besoin.

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

Ici, nous avons un algorithme poly-temps aléatoire: Évaluer en points aléatoires . Soit et . Nous produisons . Pour que cela ait une erreur au plus nous avons besoin de ce qui équivaut àPar une borne Chernoff , asm X 1 , ⋯ , X m ∈ { 0 , 1 } n α = $\phi$$m$$X_1, \cdots, X_m \in \{0,1\}^n$ε=k/2n2n⋅αkk≥| 2nα-a| =2n| α-a/2n| ,| α-a/2n| ≤ε. P[| α-a$\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$. Cela implique que, si nous choisissons (et assurons que est une puissance de ), alors avec une probabilité d'au moins , l'erreur est au plus .$m=O(1/\varepsilon^2) = \mathrm{poly}(n)$$m$$2$$0.99$$k$

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

Dans ce cas, le problème est # P-difficile: nous ferons une réduction de # 3SAT. Prenez un 3CNF sur variables. Choisissez tel que - cela nécessite . Soit sauf que est maintenant sur variables, plutôt que . Si a affectations satisfaisantes, alors a affectations satisfaisantes, car les variables "libres" peuvent prendre n'importe quelle valeur dans une affectation satisfaisante. Supposons maintenant que nous ayons tel que$\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$ - c'est-à-dire est une approximation du nombre d'assignations satisfaisantes de avec l'erreur additive . Alors Puisque est un entier, cela signifie que nous pouvons déterminer la valeur exacte de partir de . La détermination algorithmique de la valeur exacte de implique la résolution du problème # P-complet # 3SAT. Cela signifie qu'il est # P-difficile de calculer .$\hat{a}$$\phi$$k$bb a b

$$|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$$\hat{a}$

Voici une référence à Bordewich, Freedman, Lovász et Welsh qui développe ce sujet dans une certaine mesure.