Gibt es schwierige Fälle von 3-SAT, in denen in den Klauseln nur Literale verwendet werden können, die sich "in der Nähe" befinden?

22

Sei die Variable x1,x2,x3...xn . Der Abstand zwischen zwei Variablen ist definiert als d(xa,xb)=|ab|. Der Abstand zwischen zwei Literalen ist der Abstand zwischen den entsprechenden beiden Variablen.

Angenommen , ich habe eine 3-SAT - Instanz , so dass für jede Klausel (xa,xb,xc) haben wir d(xa,xb)Nd(xa,xc)Nd(xb,xc)N aus irgendeinem festen Wert N .

Konzeptionell kann man sich vorstellen, dass alle Literale physisch in einer Zeile stehen und alle Klauseln aus physischen Gründen nicht in der Lage sind, eine bestimmte Länge zu überschreiten.

Gibt es angesichts dieser Einschränkung harte Instanzen von 3-SAT? Wie klein kann ich die Nachbarschaft machen und trotzdem schwierige Instanzen finden? Was ist, wenn ich ein paar Klauseln zulasse, um die Einschränkung zu verletzen?

Mit hart meine ich, dass ein heuristischer Löser auf den schlimmsten Fall zurückgreifen würde.

IIAOPSW
quelle
2
"Mit hart meine ich, dass ein heuristischer Löser auf den schlimmsten Fall zurückgreifen würde." klingt für mich nicht gut definiert. Können wir Ihre Frage dahingehend interpretieren, ob es einen Polynom-Zeit-Algorithmus gibt, der alle derartigen 3-SAT-Instanzen löst? Oder nach der Komplexität / Härte dieses Problems fragen?
DW
"Können wir Ihre Frage dahingehend interpretieren, ob es einen Polynom-Zeit-Algorithmus gibt, der alle derartigen 3-SAT-Instanzen löst?" Ich denke, das ist was ich suche.
IIAOPSW
1
Die Lokalitätsanforderung, die Sie verwenden, wird auch als 1D "geometrisch lokal" bezeichnet und ist für Physiker die vorherrschende Bedeutung von "Lokalität". Verallgemeinert man nun Ihre Frage auf den Quantenfall und von Bits (2 Zustände) zu Partikeln mit 8 Zuständen, ist die Quantenversion Ihres Problems in der Tat QMA-vollständig ("Quanten-NP") in 1D: Siehe arxiv.org/ abs / 1312.1469 Für Qubits ist das Problem in 2D QMA-vollständig. arxiv.org/abs/quant-ph/0504050
Martin Schwarz
4
Ein Physiker kann sich also nicht unter Informatikern verstecken. Du hast mich erwischt. Warum brauchen Sie 8 Staaten? Verwenden Sie einfach Qubits, verdreifachen Sie die Nachbarschaftsgröße und verwenden Sie alle 3 Qubits, um ein Teilchen mit 8 Zuständen zu codieren.
IIAOPSW
1
Klar, aber dann hast du eine ziemlich hohe Lokalität, dh deine lokalen Operatoren überspannen viele Qubits. Diese Forschungslinie konzentrierte sich auch auf die Minimierung der Lokalität (idealerweise 2-lokal) auf Kosten höherdimensonaler Partikel und der damit verbundenen Kompromisse.
Martin Schwarz

Antworten:

30

Nein. Wenn die 3-SAT-Instanz über Klauseln verfügt, können Sie die Erfüllbarkeit in O ( m 2 N ) -Zeit testen . Da N eine feste Konstante ist, ist dies ein Polynom-Zeit-Algorithmus, der alle Instanzen Ihres Problems löst.mO(m2N)N

Der Algorithmus arbeitet in Stufen. Sei φ i die Formel bestehend aus den Sätzen, die nur Variablen aus x 1 , , x i verwenden . Sei S i{ 0 , 1 } n die Menge von Zuordnungen zu x i - N , x i - N + 1 , ... , x i , die zu einer befriedigenden Zuordnung für φ i erweitert werden können . Beachten Sie, dass bei Smφix1,,xiSi{0,1}nxiN,xiN+1,,xiφi , so können wir S i inO( 2 N )Zeitberechnen: für jedeSi1SiO(2N) versuchen wir beide Möglichkeiten für x i und prüfen, ob es erfüllt alle Klauseln von φ i , die die Variable x i enthalten ; wenn ja, addieren wir ( x i - N , (xiN1,,xi1)Si1xiφixi bis S i. Im i- ten Stadium berechnen wir S i . Sobald wir alle fertig sind m Stufen, ist die 3-SATInstanz erfüllbarwenn und nur wenn S m & ne; . Jede Etappe dauert(xiN,,xi)SiiSimSm Zeit und es gibt m Stufen, sodass die Gesamtlaufzeit O ( m 2 N ) beträgt. Dies ist in der Größe der Eingabe polynomisch und bildet somit einen Polynom-Zeit-Algorithmus.O(2N)mO(m2N)

Selbst wenn Sie zulassen, dass eine feste Anzahl von Klauseln gegen die Einschränkung verstößt, kann das Problem in polynomieller Zeit gelöst werden. Insbesondere wenn die Anzahl der Klauseln zählt, die die Bedingung verletzen, können Sie das Problem in O ( m 2 ( t + 1 ) N ) lösen , indem Sie zuerst alle möglichen Werte für die Variablen in diesen Klauseln auflisten und dann fortfahren der Algorithmus oben. Wenn t eine feste Konstante ist, ist dies die Polynomzeit. Möglicherweise gibt es effizientere Algorithmen.tO(m2(t+1)N)t

DW
quelle
16

Das Ereignisdiagramm einer SAT-Formel ist ein zweigliedriges Diagramm, das für jede Klausel und jede Variable einen Scheitelpunkt hat. Wir fügen Kanten zwischen einer Klausel und allen ihren Variablen hinzu. Wenn der Vorfallgraph die Baumbreite begrenzt hat, können wir die SAT-Formel in P festlegen, tatsächlich können wir viel mehr tun. Ihr Ereignisdiagramm ist sehr eingeschränkt. ZB ist es ein Diagramm mit begrenzter Pfadbreite, daher ist es polynomiell zeitlösbar. Das obige bekannte strukturelle Ergebnis finden Sie beispielsweise unter: https://www.sciencedirect.com/science/article/pii/S0166218X07004106 .

Saeed
quelle
1
Tatsächlich hat in diesem Fall sogar das ursprüngliche Diagramm (eine Kante zwischen zwei Scheitelpunkten, wenn sie in derselben Klausel erscheinen) die Pfadbreite begrenzt. Siehe auch (1) , auf die möglicherweise besser zugegriffen werden kann, oder @DW-Antwort, die ungefähr der gleichen Idee wie diese Algorithmen entspricht. (1) Algorithmen für das Zählen von Aussagenmodellen , Marko Samer, Stefan Szeider, J. Discrete Algorithms, Band 8, Nummer 1, Seiten 50-64, 2010.
Freitag,