Komplexität eines Constraint-Zufriedenheitsversprechens

8

(Dies ist das "obere Ende" meiner Frage von vor über 10 Monaten auf cs.stackexchange.
Diese Frage und das "untere Ende", das ich hier vor über 8 Monaten gestellt habe und auf
das ich auch ein Kopfgeld habe, sind beide unbeantwortet.
Diese sind Screenshots davon, wie dieser Beitrag aussehen sollte, falls er nicht richtig gerendert wird.)


Anfang des Motivationsabschnitts:

Ich begann mich zu fragen, ob Schäfers Dichotomiesatz
auf Versprechungsbeschränkungen erweitert werden kann oder nicht. Als Teil davon suchte ich nach
der einfachsten Versprechungsbeschränkung, für die die Antwort nicht trivial ist:

Um zu vermeiden, dass der Satz von Schaefer bereits gilt, muss es mindestens ein Eingabetupel geben, für das das Versprechen fehlschlägt. Aus dem gleichen Grund wie dieser Satz müssen all-true und all-false NEIN geben, und es muss mehr als eine Eingabe geben, die JA ergibt. Insbesondere müssen mehr als vier mögliche Eingaben vorhanden sein, sodass die Versprechen-Einschränkung mindestens drei Variablen umfassen muss. Um eine einfache zu erhalten, nehmen wir an, dass sie über genau 3 Variablen liegt und symmetrisch ist, dh nur davon abhängt, wie vielevon seinen Eingaben sind wahr, nicht welche das sind. In diesem Fall gibt entweder 2-wahr JA und das Versprechen schlägt für 1-wahr fehl, 1-wahr gibt JA und das Versprechen schlägt für 2-wahr fehl. Durch einfaches Umdrehen jeder Variablen sind diese äquivalent schwer. Um eine kürzere formale Aussage und einen "schöneren" Namen zu erhalten, verwende ich letztere, dh genau 1-wahr gibt JA und das Versprechen schlägt für 2-wahr fehl.

Ende des Motivationsabschnitts

Meine Frage


Sei "positiv 1,2-in-3-SAT" das Versprechen Problem.

Eingänge haben die Syntax von 3-SAT ohne Negationen
müssen JA ausgeben, wenn: der Eingang 1-in-3-erfüllbar ist,
muss NEIN ausgegeben werden, wenn : Die Eingabe ist nicht NAE-erfüllbar

.


Wie komplex ist das Problem?

Sie können wählen, ob eine Variable in einer einzelnen Versprechen-Einschränkung zweimal vorkommen kann oder nicht.


(Eine Variable, die dreimal in einer einzelnen Versprechen-Einschränkung vorkommt,
würde sie automatisch zu einer Must-Output-NO-Instanz machen.)

Offensichtlich ist die Identitätsfunktion eine Reduktion vom Versprechen-Problem zum positiven 1-in-3-SAT
und zum positiven NAE-SAT, so dass GC (O (m), coNLOGTIME ) das Versprechen-Problem lösen kann.
Es gibt jedoch eine scheinbar triviale Beobachtung, die zu einer
kombinatorischen Behinderung "einfacher" NP-Härtebeweise für positive 1,2-in-3-SAT führt:


Für jeden Satz von Variablen, der mindestens eine Versprechen-Einschränkung mehr als einmal erfüllt,
Es gibt keine 1-in-3-zufriedenstellende Zuordnung, in der diese Variablen alle wahr sind.
Umgekehrt gilt für jeden Satz von Variablen, der jede Versprechen-Einschränkung höchstens einmal erfüllt, für jeden
Eine 1-in-3-zufriedenstellende Zuweisung, die möglicherweise so geändert wird, dass alle Variablen in diesem Satz wahr sind, ergibt eine NAE-zufriedenstellende Zuweisung. Insbesondere ist die Disjunktion von zwei 1-in-3-erfüllenden Zuweisungen
immer eine NAE-zufriedenstellende Zuweisung. Um die Konsequenzen
davon zu erläutern, nehmen wir an , dass ein positives 1,2-in-3-SAT ein Gadget hat , das eine Versprechen-Einschränkung C implementiert, so dass
das Gadget "die Variablen von C auf die gleiche Weise darstellt und interpretiert", dh






forward


forward

backward
backward

. In diesem Fall hat C für jede der Variablen x und y von C einen JA-Eingang, so dass (x, y) = (a, b) und
einen JA-Eingang, so dass (x, y) = (b, a), dann hat es eine Eingabe, so dass x = y, aber es gibt kein NEIN.
Insbesondere können solche Geräte nicht einmal das Färben von Versprechen implementieren .


Außerdem ist das Komplement einer 1-in-3-zufriedenstellenden Zuweisung immer eine NAE-zufriedenstellende Zuweisung, die den Arten von Gadgets, die ein positives 1,2-in-3-SAT haben könnte, schwächere Einschränkungen auferlegt.






m(2 o (m))/m

Gemeinschaft
quelle
Nehmen wir an, wir erhalten einen booleschen Ausdruck F in 3-CNF, wobei keines der Literale negiert wird. Ok ... Uns wird versprochen, dass es immer eine Lösung gibt, da Sie möchten, dass es JA = 1-in-3-SAT und NEIN = NAE-SAT ist. Was Sie jedoch vermissen, ist, dass F gleichzeitig 1-in-3-SAT und NAE-SAT sein kann. Zum Beispiel kann es eine zufriedenstellende Wahrheitszuweisung haben, bei der genau 1 Literal erfüllt ist, so dass es 1-in-3-SAT ist, aber dies bringt es auch in NAE-SAT, da die Literale aller Klauseln nicht alle True oder sind Falsch.
Tayfun Pay
Wie wäre es mit JA = 1 in 3 SAT, NEIN = 2 in 3 SAT. ? :-)
Tayfun Pay
"das bringt es auch in NAE-SAT", was bedeutet, dass es nicht NAE-befriedigend ist, also sehe ich das Problem mit dem, was ich geschrieben habe, nicht.
Ja. Ich habe gerade gesehen, dass Sie ~ NAE-SAT wollen ... Sie möchten also, dass alle Literale jeder Klausel entweder alle wahr oder alle falsch sind. Richtig?
Tayfun Pay
Alle wahren Teile sind nur möglich, wenn Sie Negationen haben ... Und dieselbe Variable zweimal mit entgegengesetzter Polarität innerhalb derselben Klausel.
Tayfun Pay

Antworten:

2

In Bezug auf die Frage, ob Shaefers Dichotomiesatz (oder allgemeiner die kürzlich von Bulatov und Zhuk bewiesene Feder-Vardi-Vermutung ) verallgemeinert werden kann, um Probleme zu versprechen: Die Komplexität von versprochenen CSPs ist derzeit ein heißes Forschungsthema. Es ist immer noch sehr offen, ob es eine solche Dichotomie auch für Boolesche PCSPs gibt. Es sind jedoch Teilergebnisse bekannt, insbesondere Brakensiek und Guruswami [1] beweisen eine Dichotomie für symmetrische boolesche PCSPs, die die Negation von Variablen ermöglichen.

x1x2+x3xL1+xL

Algorithmus 1:

C3xi¯1xiLC

u+v+w=1
{u,v,w}C(x1,,xn)LC

C

xi={1xi1,0xi0
C

(Beide Behauptungen sind einfach zu überprüfen.)

Algorithmus 2:

PCLC

0xi1
xi

iPC{xi=0}PC{xi=1}C

C

3CC

Referenz:

[1] Joshua Brakensiek und Venkatesan Guruswami, Promise Constraint Satisfaction: Algebraische Struktur und eine symmetrische boolesche Dichotomie , arXiv: 1704.01937 [cs.CC].

Emil Jeřábek
quelle