Was ist die Komplexität von Median-SAT?

Sei eine CNF-Formel mit Variablen und Sätzen. Es sei eine Variablenzuordnung und die Anzahl von Klauseln, die durch eine Variablenzuordnung zu erfüllt sind. . Definieren Sie dann Median-SAT als das Problem der Berechnung des Medianwerts von über alle . Wenn beispielsweise eine Tautologie ist, lautet die Lösung für Median-SAT da unabhängig von der Zuweisung jede Klausel erfüllt wird. Im Fall von $\varphi$ $n$ $m$ $t \in \{ 0,1 \}^n$ $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ $\varphi$ $f_{\varphi}(t)$ $t \in \{ 0,1 \}^n$ $\varphi$ $m$ $\overline{SAT}$ Die Lösung für Median-SAT könnte irgendwo zwischen und . $0$ $m-1$

Diese Frage tauchte auf, als ich über zwei natürliche Erweiterungen von SAT, MAX-SAT und #SAT nachdachte und die Schwierigkeit des sich daraus ergebenden Problems abschätzte, wenn sie zusammengesetzt würden. Für MAX-SAT müssen wir eine bestimmte Variablenzuordnung finden, um die Anzahl der Variablen zu maximieren, die von erfüllt werden . Für #SAT müssen wir zählen, wie viele Zuweisungen alle Klauseln von erfüllen . Diese Variante wird hauptsächlich als Erweiterung von #SAT (und tatsächlich von #WSAT ) ausgeführt, behält jedoch einen Teil des MAX-SAT-Geschmacks bei, indem wir die Anzahl der zufriedenen Klauseln zählen, anstatt nur zu entscheiden, ob sie alle zufrieden sind oder nicht nicht. $\varphi$ $m$ $\varphi$

Dieses Problem scheint schwerer zu sein als #SAT oder #WSAT. Für jede Variablenzuweisung entscheidet #SAT über das Boolesche Problem, ob diese Zuweisung erfüllt oder nicht, während Median-SAT festlegt, "inwieweit" in Bezug auf die Anzahl der Klauseln erfüllt ist, die eine Zuweisung erfüllt. $\varphi$ $\varphi$

Mir ist klar, dass dieses Problem etwas willkürlich ist. Die Berechnung des Durchschnitts oder der Modusanzahl von Klauseln, die von jeder Variablenzuweisung erfüllt werden, scheint die gleiche Qualität zu erfassen. Wahrscheinlich auch viele andere Probleme.

Wurde dieses Problem untersucht, vielleicht unter einem anderen Deckmantel? Wie schwer ist es im Vergleich zu #SAT? Mir ist a priori nicht klar, dass Median-SAT sogar in FPSPACE enthalten ist, obwohl es in FEXPTIME enthalten zu sein scheint.

cc.complexity-theory sat counting-complexity Huck Bennett
quelle

Es ist in

: Für jedes

wir die Anzahl von Zuweisungen, die mindestens

Klauseln erfüllen , unter Verwendung eines

Orakels zählen.

F P^{# P} \subseteq F P S P A C E

$FP^{\#P}\subseteq FPSPACE$

k \leq m

$k\leq m$

k

$k$

Colin McQuillan

@Colin daraus eine Antwort machen?

Suresh Venkat

Ja, das wäre eine gute Antwort. Könnten Sie näher erläutern, wie das #P-Orakel abgefragt werden kann, um zu überprüfen, ob die

Klauseln erfüllt sind? Ich konnte nicht herausfinden, wie man es effizient macht.

k \leq m

$k \leq m$

Huck Bennett

@ Tsuyoshi, was ist Ihre Definition von SAT? Erlauben wir die Wiederholung von Klauseln? oder Literale und / oder Variablen in einer bestimmten Klausel? Denn wenn Sie keine Wiederholung von Literalen und / oder Variablen in einer bestimmten Klausel zulassen, können Sie keine CNF-Formel haben, die eine Tautologie ist.

Tayfun Pay

@Tayfun - Ich habe diese Frage tatsächlich gestellt, Tsuyoshi half bei einem kleinen Schnitt. Sie haben Recht mit einer Tautologie in einer CNF-Formel, die wiederholte Literale erfordert. Jede SAT-Variante wäre interessant, CNF-SAT ohne Wiederholung in Sätzen (in diesem Fall sind Tautologien nicht möglich) oder CIRCUIT-SAT allgemeiner. Ich denke nicht, dass diese Wahl den Geschmack der Frage ändert.

Huck Bennett

Antworten:

Wenn eine Instanz von SAT, eine Ganzzahl und eine Variablenzuweisung gegeben sind, können wir in polynomieller Zeit entscheiden, ob genau Klauseln erfüllt sind, indem wir einfach die Anzahl der erfüllten Klauseln zählen und testen, ob diese Anzahl gleich . Daher können wir mit einem #P- Orakel die Gesamtzahl der variablen Zuordnungen berechnen, die genau Klauseln erfüllen . $k$ $k$ $k$ $k$

Wie Max-SAT kann auch Median-SAT mit einem Orakel in Polynomzeit berechnet werden . Dies zeigt, dass das Problem in . $\#P$ $FP^{\#P} \subseteq FPSPACE$

Colin McQuillan
quelle

Du hast absolut recht. Dies ist ein sehr sauberes Argument, und ich denke, dass es aus der Definition von #P ziemlich offensichtlich ist. Ich habe etwas gelernt.

Huck Bennett

Lassen Sie mich noch etwas näher darauf eingehen: Colins Aussage, dass wir, weil wir in polynomialer Zeit bestimmen können, ob eine bestimmte Variablenzuweisung

Klauseln erfüllt , eine Variablenzuweisung nicht deterministisch erraten und dann zählen können, wie viele Akzeptanzpfade (dh Akzeptieren von Variablenzuweisungen) diese Abfrage aufweist hatte mit dem

Orakel (per Definition von

). Indem wir k = 1 bis m durchlaufen, können wir die mittlere Anzahl der in

erfüllten Klauseln zählen .

k

$k$

# P

$\#P$

# P

$\#P$

F P^{# P}

$FP^{\#P}$

Huck Bennett

Dieses Problem kann gelöst werden , indem Anrufungen eines Orakels für MAJSAT. $\lceil \lg m+1 \rceil$

Es sei der gewünschte Medianwert für . Definieren Sie für festes die Formel so, dass es für die Zuweisung wenn mindestens der Klauseln von erfüllt . Beachten Sie, dass Sie bei in CNF-Form und bei leicht in CNF-Form in Polynomzeit konstruieren können. $M(\varphi)$ $\varphi$ $k$ $\psi_k$ $x$ $x$ $k$ $\varphi$ $\varphi$ $k$ $\psi_k$

Angenommen, wir hatten ein Orakel für MAJSAT. Eine Abfrage der Formel würde uns sagen, ob die Mehrzahl der Zuweisungen die Formel wahr macht oder äquivalent dazu, ob . Um also zu lernen , wenden Sie eine binäre Suche an (beginnen Sie mit , und erhöhen oder verringern Sie dann entsprechend den Ergebnissen des Orakels). Nach Iterationen zeigt die binäre Suche den Wert von $\psi_k$ $\psi_k$ $M(\varphi) \ge k$ $M(\varphi)$ $k=m/2$ $k$ $\lg m+1$ $M(\varphi)$ . Jede Iteration erfordert eine Anfrage an unser Orakel für MAJSAT.

DW
quelle