Polynomkern für

Das parametrisierte Problem mit k-FLIP SAT ist wie folgt definiert:

Input: eine 3-CNF Formel mit Variablen und einer Wahrheits Zuordnung Parameter: Frage: kann man die Zuordnung Transformation in eine satifying Zuordnung für Flipping den Wahrheitswert höchstens Variablen? $\varphi$ $n$ $\sigma : [n] \to \{0,1\}$
$k$
$\sigma$ $\sigma'$ $\varphi$ $k$

Das Problem liegt ~~eindeutig~~ in der FPT ( Stefan Szeider: Die parametrisierte Komplexität der lokalen k-Flip-Suche nach SAT und MAX SAT. Diskrete Optimierung 8 (1): 139-145 (2011) )

Lässt es einen Polynomkern zu? (unter angemessenen Komplexitätsannahmen)

Die jüngsten Cross-Composition-Techniken (siehe Hans L. Bodlaender, Bart MP Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition" ) scheinen für dieses Problem nicht geeignet zu sein. Und sie scheinen auch für ähnliche Probleme unbrauchbar zu sein, bei denen gefragt wird, ob eine bestimmte Lösung für ein NP-hartes Problem aus einer bestimmten Instanz durch lokale Suche gefunden werden kann (wobei die Suche unter einem natürlichen Entfernungsmaß auf die Nachbarn der angegebenen Instanz beschränkt wird).

parameterized-complexity fixed-parameter-tractable Marzio De Biasi
quelle

Cool, aber warum ist dieses Problem eindeutig FPT? Wenn Sie es 2-CNF mit genau k variablen Flips anstelle von höchstens machen, dann glaube ich, dass das Problem fpt-äquivalent zu k-Clique ist. Ich habe an einem Papier gearbeitet, das einige Ergebnisse zu Problemen mit genauem K-Flip enthält.

Michael Wehar

Ich denke, zu sagen, dass es in FPT ist, bedeutet, dass es in

Zeit lösbar ist .

f (k) \cdot n^{O (1)}

$f(k) \cdot n^{O(1)}$

Michael Wehar

Ich denke, zu sagen, dass es in XP ist, bedeutet, dass es in

Zeit lösbar ist .

n^{f (k)}

$n^{f(k)}$

Michael Wehar

Ich kenne die Beziehung zwischen dem exakten K-Flip-Problem und dem Atmost-K-Flip-Problem nicht. Ich dachte anfangs, dass Sie sagten, das Problem des atmost-k-flip sei einfacher in dem Sinne, dass atmost-k-flip FPT ist. Ich sage einfacher, weil Exact-K-Flip kein FPT sein kann, wenn die ETH nicht falsch ist. Der Grund dafür ist, dass es der k-Clique entspricht und bekannt ist, dass

-Zeitalgorithmen für die k-Clique implizieren, dass die ETH falsch ist.

f (k) \cdot n^{O (1)}

$f(k) \cdot n^{O(1)}$

Michael Wehar

@MichaelWehar: ops, du hast recht (ich lösche den falschen Narren-Kommentar), die Frage muss poliert werden (ich habe das Problem als "höchstens k FLIPS" definiert). SO SCHNELL WIE MÖGLICH Werfe ich mir die Artikel an (einer von ihnen sollte Stefan Szeider sein, "Die parametrisierte Komplexität der lokalen k-Flip-Suche nach SAT und MAX SAT"), in denen gesagt wird, dass k-FLIP SAT ist FPT für Klauseln mit begrenzter Größe.

Marzio De Biasi

Das Problem hat keinen Polynomkern, es sei denn, NP ist in coNP / poly. Die Cross-Composition-Technik aus unserer Arbeit ist nicht trivial anwendbar.

$(G_1,k), (G_2, k), \ldots, (G_t, k)$ $k$ $n$ $k$ $O(k + \log t)$ $k$ $k$ $t$

$G_i$ $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$ $u_i$ $i \in [t]$ $G_i$ $\{v_{i,x}, v_{i,y}\}$ $G_i$ $(v_{i,x} \vee v_{i,y} \vee \neg u_i)$ $i$ $u_i$ werden auf false gesetzt, damit diese Klauseln alle erfüllt sind. Um das ODER-Verhalten in die Komposition einzubauen, werden wir die Formel erweitern, um sicherzustellen, dass eine zufriedenstellende Zuweisung mindestens einen Selektor auf true setzt und dann auch eine Scheitelpunktabdeckung des ausgewählten Graphen bilden muss.

$t$ $t$ $\log t$ $1$ $t$ $i$ $u_i$ $i$ $x$ $y$ $z$ $(\neg x \vee y \vee z)$ $(x \rightarrow (y \vee z))$ $x$

$k'$ $(k + \log t + 1)$ $k'$ $G_i$ $k$

$G_i$ $k$ $k$ $k$ $u_i$ $i$ $\log t$ $i$ $G_{i'}$ $i' \neq i$ $u_{i'}$ $G_i$

$k + \log t + 1$ $u_i$ $u_i$ $1 + \log t$ $u_i$ $G_i$ $\neg u_i$ $G_i$ $1 + \log t$ $k$ $k$ $G_i$

Bart Jansen
quelle

Dieses Papier gibt stärkere Konsequenzen aus einer solchen Komprimierung.

Vielen Dank!!! (Ich habe sofort "et al." Aus der Referenz entfernt ;-). Netter Beweis (IMO sollten Sie ihn in einem Papier veröffentlichen).

Marzio De Biasi

Polynomkern für

Antworten: