Komplexität eines Constraint-Zufriedenheitsversprechens

(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$
^{$\hspace{.02 in}$}

$forward$

$backward$^{$\hspace{.02 in}$}
$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$$\hspace{-0.03 in}\big(\hspace{-0.04 in}$2 ^{o (m)}$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$$m$

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.

$x_1-x_2+x_3-\dots-x_{L-1}+x_L$

Algorithmus 1:

$C$$3$$\overline{x_i}$$1-x_i$$L_C$

$C$

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

Algorithmus 2:

$P_C$$L_C$

$i$$P_C\cup\{x_i=0\}$$P_C\cup\{x_i=1\}$$C$

$C$

$3$$C$$C$

Referenz:

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