Annäherung an # P-harte Probleme

9

Betrachten Sie das klassische # P-vollständige Problem # 3SAT, dh die Anzahl der Bewertungen zu zählen, um einen 3CNF mit Variablen erfüllbar zu machen. Ich interessiere mich für die additive Approximierbarkeit. Natürlich gibt es einen trivialen Algorithmus, um einen -Fehler zu erzielen , aber wenn , ist es möglich, einen effizienten Approximationsalgorithmus zu haben, oder dieses Problem ist auch # P-schwer ? $n$ $2^{n-1}$ $k<2^{n-1}$

approximation-algorithms sat counting-complexity approximation-hardness user0928
quelle

Wenn , dann gibt es einen Polyzeitalgorithmus mit dem additiven Fehler . Wenn , würde es einen randomisierten Polyzeitalgorithmus mit dem additiven Fehler . Wenn signifikant kleiner (aber nicht polynomiell klein) ist, würde ich erwarten, dass es NP-hart ist, aber nicht # P-hart, da die # P-Härte normalerweise davon abhängt, dass es sich um eine exakte Berechnung handelt.

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

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

k

$k$

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

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

k

$k$

k

$k$

Thomas

Könnten Sie die ersten beiden Ansprüche angeben? Entschuldigung, ich bin ein Anfänger ...

user0928

10

Wir sind an additiven Annäherungen an # 3SAT interessiert. dh wenn ein 3CNF auf Variablen gegeben ist, zählen Sie die Anzahl der erfüllenden Zuweisungen (nennen Sie dies ) bis zum additiven Fehler . $\phi$ $n$ $a$ $k$

Hier sind einige grundlegende Ergebnisse dafür:

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

Hier gibt es einen deterministischen Polyzeitalgorithmus: Sei . Bewerten Sie nun auf beliebigen Eingaben (z. B. die lexikographisch ersten Eingaben). Angenommen, dieser Eingaben erfüllen . Dann kennen wir da es mindestens befriedigende Aufgaben gibt, und da es mindestens unbefriedigende Aufgaben gibt. Die Länge dieses Intervalls beträgt . Wenn wir also den Mittelpunkt ausgeben, liegt dieser innerhalb von $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$ der richtigen Antwort, wie erforderlich.

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

Hier haben wir einen randomisierten Poly-Time-Algorithmus: Bewerten Sie an zufälligen Punkten . Sei und . Wir geben . Damit dies höchstens fehlerhaft ist, benötigen wir wasDurch eine Chernoff gebunden , als $\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} α - a | = 2^{n} | α - a / 2^{n} |,

$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$

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

$|\alpha - a/2^n| \leq \varepsilon.$

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

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

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

$\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$ . Dies impliziert, dass, wenn wir wählen (und sicherstellen, dass eine Potenz von ) , der Fehler mit einer Wahrscheinlichkeit von mindestens höchstens ist .

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

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

m

$m$

2

$2$

0.99

$0.99$

k

$k$

Fall 3: für $k=2^{cn + o(n)}$ $c < 1$

In diesem Fall ist das Problem # P-schwer: Wir werden eine Reduzierung von # 3SAT vornehmen. Nehmen Sie einen 3CNF für Variablen. Wählen Sie so, dass - dies erfordert . Es sei außer dass jetzt auf Variablen und nicht auf . Wenn hat erfüllenden Belegungen, dann hat erfüllenden Belegungen als „frei“ Variablen einen beliebigen Wert in zufriedenstellender Zuordnung erfolgen kann. Nehmen wir nun an, wir haben so, dass $\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$ - das heißt ist eine Annäherung an die Anzahl der erfüllenden Zuweisungen von mit dem additiven Fehler . Dann Da eine ganze Zahl ist, bedeutet dies, dass wir den genauen Wert von aus bestimmen können . Das algorithmische Bestimmen des genauen Wertes von beinhaltet das Lösen des # P-vollständigen Problems # 3SAT. Dies bedeutet, dass es # P-schwer ist, zu berechnen . $\hat{a}$ $\phi$ $k$

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

b

$b$

b

$b$

\hat{a}

$\hat{a}$

b

$b$

\hat{a}

$\hat{a}$

Thomas
quelle

4

Hier ist ein Verweis auf Bordewich, Freedman, Lovász und Welsh , der dieses Thema in gewissem Maße entwickelt.

Martin Schwarz
quelle

Annäherung an # P-harte Probleme

Antworten: