Begrenzte Anzahl variabler Vorkommen in 1-in-3-SAT

Gibt es ein bekanntes Ergebnis für die Komplexitätsklasse 1-in-3-SAT mit einer begrenzten Anzahl variabler Vorkommen?

Ich habe mir mit Peter Nightingale die folgende sparsame Reduktion ausgedacht, aber ich möchte etwas zitieren, wenn dies bekannt ist.

Hier ist der Trick, den wir uns ausgedacht haben. Dies zeigt, dass 1-in-3-SAT, begrenzt auf 3 Vorkommen pro Variable, NP vollständig und #P vollständig ist (da 1-in-3-SAT vollständig ist) , während 3-SAT, begrenzt auf 3 Vorkommen, in P ist

Nehmen wir an, wir haben mehr als drei Vorkommen von x. Angenommen, wir brauchen 6. Dann werden wir 5 neue Variablen x2 bis x6 einführen, die x entsprechen, und zwei neue Variablen d1 und d2, die mit den folgenden 6 neuen Klauseln garantiert falsch sind:

x  -x2 d1
x2 -x3 d1
x3 -x4 d1
x4 -x5 d2
x5 -x6 d2
x6 -x  d2

Offensichtlich ersetzen wir jedes Vorkommen von x nach dem ersten durch xi für einige i. Das ergibt drei Vorkommen von jeweils xi und d.

Das obige setzt jedes di auf false und alle xi auf den gleichen Wert. Um dies zu sehen, muss x wahr oder falsch sein. Wenn es wahr ist, setzt die erste Klausel x2 wahr und d1 falsch, und dies verbreitet sich dann über die Klassen. Wenn x falsch ist, setzt die letzte Klausel x6 falsch und d2 falsch und verbreitet die Klauseln. Es ist offensichtlich stark sparsam, so dass das Zählen erhalten bleibt.

Meines Wissens sind die aktuellen "Grenzen" festgelegt in:

Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw: XSAT und NAE-SAT linearer CNF-Klassen. Discrete Applied Mathematics 167: 1-14 (2014)

Siehe auch Schmidts These: Computerkomplexität von SAT, XSAT und NAE-SAT für lineare und gemischte Horn-CNF-Formeln

$k$$CNF^l_+$$k$$CNF^l$$k, l \geq 3$

$3$$CNF^3$$l=3$

Beachten Sie, dass der Satz auch die NP-Vollständigkeit des stärkeren monotonen Falls ( beweist.$CNF_+$

(Ich verstehe, dass dies eine späte Antwort sein muss; ich schreibe für zukünftige Leser)

In der Literatur gibt es ein immer stärkeres Ergebnis.

Cubic Planar Positive 1-in-3-Zufriedenheit ist in Moore und Robson, Probleme mit harten Fliesen mit einfachen Fliesen , NP-vollständig . (Sie sagen "monoton" statt "positiv". Siehe Anmerkung zuletzt hinzugefügt)

Das erwähnte Ergebnis ist stärker als das Ergebnis in Schmidts These, da hier der Graph der Formel auf planar beschränkt ist. (Der Zustand ist in der Tat stärker: Sie ergeben eine bestimmte Art der Einbettung, die als geradlinige Einbettung bezeichnet wird.)

$G_B$$B=(X,C)$$X\cup C$$E:= \{ x_iC_j\ :\ $$x_i$$C_j$$\}$$X$$C$

$B=(X,C)$$X$$C$$X$$G_B$$B$
$X$$C$

Beachten Sie, dass jede Klausel genau 3 verschiedene Variablen enthält und jede Variable in genau 3 Klauseln erscheint.

Siehe Tippenhauers These zu Planar 3-SAT und seinen Varianten (2016) für sat-Varianten, die die Anzahl variabler Vorkommen einschränken.
Hinweis: Nach der Veröffentlichung dieser Arbeit wurden einige Varianten entdeckt.

Hinweis hinzugefügt: Das Ergebnis von Moore und Robson hat gezeigt, dass die kubisch-planare positive 1-in-3-Zufriedenheit NP-vollständig ist. (Das heißt, die Boolesche Formel ist nicht nur monoton, sondern auch positiv (dh überhaupt keine negierten Literale)). Leider wurde in vielen frühen Veröffentlichungen der Begriff "monoton" verwendet, um "positiv" zu bedeuten. Die Reduktion durch Moore und Robson führt keine negierten Literale ein. Ihre Reduktion ergibt sich aus der planaren 'monotonen' 1-in-3-Zufriedenheit in Laroches Artikel Die planare 1-in-3 -Zufriedenheit ist NP-vollständig . Ich konnte dieses Papier nicht bekommen, aber höchstwahrscheinlich meinte Laroche auch positiv, indem er "monoton" sagte. Auch wenn er dies nicht so gemeint hat, können wir die planare positive 1-in-3-Zufriedenheit von Mulzer und Rote 'verwenden. als Quellproblem stattdessen.

Siehe diese Antwort für eine Frage in cs.se.