MIN-2-XOR-SAT und MAX-2-XOR-SAT: Sind sie NP-hart?

13

Was ist die Komplexität von MIN-2-XOR-SAT und MAX-2-XOR-SAT ? Sind sie in P? Sind sie NP-hart?

Um dies genauer zu formalisieren, lassen Sie

Φ(x)=inCi,

wobei x=(x1,,xm) und jede Klausel Ci von der Form (xixj) oder (xi¬xj) .

Das 2-XOR-SAT Problem besteht darin, eine Zuordnung zu x zu finden , die Φ erfüllt . Dieses Problem liegt in P , da es einem linearen Gleichungssystem mod 2 .

Das MAX-2-XOR-SAT Problem besteht darin, eine Zuordnung zu x zu finden , die die Anzahl der erfüllten Klauseln maximiert. Das MIN-2-XOR-SAT Problem besteht darin, eine Zuordnung zu x zu finden , die die Anzahl der erfüllten Klauseln minimiert. Was sind die Komplexitäten dieser Probleme?

Inspiriert von Ist MIN oder MAX-True-2-XOR-SAT NP-hart?

DW
quelle

Antworten:

6

Entschuldigung für die Beantwortung eines alten Beitrags

Das Problem der Bestimmung , ob ein MONOTONE-2-XOR-TV (alle Klauseln sind von der Art ) Instanz erfüllbar ist , kann zur Bestimmung des Problems reduziert werden , wenn ein Graph ist zweiteiligen, sehen dies .(xixj)

Dazu erstellen wir für jedes Literal der Formel einen Graphen mit einem Knoten und verbinden jedes Literal mit einem anderen, wenn sie sich in derselben Klausel befinden (Kanten sind Klauseln).G

Zum Beispiel:

Wenn wir eine unbefriedigende Formel haben, die (x1x2)(x1x3)(x2x3)(x1x4)

Wir haben eine Grafik wie diese:

grafo no bipartito

das ist nicht zweiteilig

Es gibt drei Klauseln, die erfüllt werden können, und deshalb müssen wir nur eine Kante beseitigen

kk

Um die Reduktion durchzuführen, erstellen wir einfach ein neues Literal für jeden Scheitelpunkt und eine Klausel für jede Kante, die zwei Literale verbindet

Zum Beispiel:

Wir haben diese Grafik,

grafo no bipartito 2

(x1x2)(x1x4)(x2x4)(x2x3)(x4x5)(x3x5)

kk

Rotia
quelle
1
Sie sollten die Implikation explizit machen: Da MAX-CUT NP-Hard ist, bedeutet die Reduktion auf MAX-XORSAT, dass es auch NP-Hard ist.
Antimon
-1

(xixj)xixixjxixjxixj ist wahr, wenn den entsprechenden Eckpunkten im Diagramm unterschiedliche Farben zugewiesen wurden.

Wenn alle Scheitelpunkte des Diagramms mit zwei Farben eingefärbt werden können und keinem von zwei Scheitelpunkten mit einem gemeinsamen Kantenanteil dieselbe Farbe zugewiesen wird, ist die Gleichung erfüllt.

Ein Diagramm ist jedoch zweifarbig, wenn es sich um ein zweiteiliges Diagramm handelt. Die Bestimmung, ob ein Graph zweigeteilt ist, kann in Polynomzeit erfolgen. Daher liegt das Problem in P, denn wenn wir in Polynomzeit feststellen können, dass der Graph ein zweiteiliger Graph ist, ist er lösbar, andernfalls ist er nicht lösbar.

jcod0
quelle
1
(xixj)(xk¬xl)k,l(xk¬xl)
2
Dies bringt mich zu einem ernsteren Problem mit Ihrer Antwort. Das Problem besteht nicht darin, festzustellen, ob die Formel erfüllt werden kann; Das Problem besteht darin, eine Zuordnung zu identifizieren, die die maximale / minimale Anzahl von Klauseln erfüllt. Ihr Algorithmus testet nur, ob die Formel erfüllt werden kann. Somit löst es 2-XOR-SAT, löst jedoch nicht MIN-2-XOR-SAT oder MAX-2-XOR-SAT - aber ich wusste bereits, dass 2-XOR-SAT in P ist, wie in erläutert die Frage. Habe ich etwas falsch verstanden?
DW
xixk
1
Aber ich sehe immer noch nicht, wie dies meinen zweiten Kommentar anspricht. Sie haben einen Sonderfall eines Problems gelöst, nach dem ich nicht gefragt habe. Kurz gesagt, diese Antwort beantwortet nicht die Frage, die ich gestellt habe.
DW