Wie verwende ich die kanonische Reihenfolge, um die Symmetrie bei der SAT-Codierung des Pigeonhole-Problems zu verringern?

In der Arbeit "Effiziente CNF-Codierung zur Auswahl von 1 aus N Objekten" stellen die Autoren ihre "Commander Variable" -Technik zur Codierung der Einschränkung vor und sprechen dann über das Pigeonhole-Problem.

Da mein Fehler möglicherweise im Verständnis auf niedrigerer Ebene besteht, möchte ich erklären, was ich zu wissen glaube, bevor ich die Frage stelle:

Sei und die Anzahl der Tauben und Löcher. Die naive Codierung verwendet eine Satzvariable , die wahr ist, wenn die Taube in das Loch gelegt werden soll. Die Klausel erzwingt, dass Taube 1 genau ein Loch besetzen muss; Für die anderen Tauben werden identische Klauseln hinzugefügt. Die Klausel erzwingt, dass nicht mehr als eine Taube Loch 1 besetzt; Für die verbleibenden Löcher werden identische Klauseln hinzugefügt.$m$$n$$X_{i,j}$$i'th$$j'th$$ExactlyOne(X_{1,1}, X_{1,2}, ..., X_{1,n})$$AtMostOne(X_{1,1}, X_{2,1}, ..., X_{m,1})$

Wenn es mehr Tauben als Löcher gibt (m> n), ist das Problem unlösbar (für Menschen offensichtlich), aber der SAT-Löser "sieht" diese Tatsache nicht. Wenn es keinen Weg findet, Tauben zu platzieren , sucht es einen Versuch mit Tauben . Es versteht nicht, dass die Reihenfolge der Tauben irrelevant ist. Das Papier nennt diese Symmetrie unter anderem.$1,2,3,..,m$$2,1,3,...,m$

Fälle, in denen ist, werden als anstrengender Test für die Fähigkeit eines SAT-Lösers verwendet, Unzufriedenheit festzustellen.$m=n+1$

Das Papier schlägt vor, die Symmetrie zu durchbrechen, indem die Ordnung der Tauben durchgesetzt wird. Die Taube muss in ein Loch vor dem Loch der Taube (dh die Taube in Loch muss eine kleinere Anzahl haben als die Taube in Loch ). Dann heißt es enttäuschenderweise: "Aus Platzgründen beschreiben wir die Codierung in kanonischer Reihenfolge nicht explizit im Detail, aber die Anzahl der generierten Klauseln liegt in der Größenordnung "$i$$i+1$$j$$j+1$$O(n*log(n))$

Meine Frage ist also: Was haben sie getan, um diese Ergebnisse zu erzielen?

Ich möchte die Variablen als Bitfolge behandeln, die numerisch die Auswahl der Taube angibt Loch 1 und so weiter. Folgen Sie diesem mit Komparatoren, um den Vorschlag des Papiers durchzusetzen. Meine naive Komparatorkonstruktion erfordert jedoch m Klauseln, eine für jedes Bit (von zunehmend hässlicher Größe). Hilfe! :) :)$\{X_{1,1}, X_{2,1}, ..., X_{m,1}\}$$n-1$

Sei die Anzahl der Tauben und die Anzahl der Löcher. Lassen Sie die Satzvariablen ... die binäre Darstellung von codieren, wenn die te Taube in das te Loch gelegt wird. (Beispiel: Wenn Taube 1 in Loch 10 platziert wurde, ist , was binär 1001 ist. Also = wahr, = falsch, = falsch und = wahr.)$m$$n$$B_{i,0}$$B_{i,log(n)}$$j-1$$i$$j$$j - 1 = 9$$B_{1,3}$$B_{1,2}$$B_{1,1}$$B_{1,0}$

Erzwingen Sie eine bestimmte Reihenfolge der Tauben in den Löchern, indem Sie verlangen, dass das von den Variablen codierte Loch kleiner als das von . Die Codierungen werden wie erwartet verglichen:$B_{i}$$B_{i+1}$

$B_{i,log(n)}$ < ODER = UND < ODER = UND = UND < ODER ... $B_{i+1,log(n)}$

$B_{i,log(n)}$$B_{i+1,log(n)}$$B_{i,log(n)-1}$$B_{i+1,log(n)-1}$

$B_{i,log(n)}$$B_{i+1,log(n)}$$B_{i,log(n)-1}$$B_{i+1,log(n)-1}$$B_{i,log(n)-2}$$B_{i+1,log(n)-2}$

... nach dem Muster, dass die höchstwertigen Bits äquivalent sein dürfen, solange das nächste Bit rechts kleiner ist als das der nächsten Taube. Pro Komparator und -Komparatoren gibt es Konjunktionen , wodurch die erwarteten zusätzlichen Klauseln erhalten werden.$O(log(n))$$O(m)$$O(m * log(n))$

Die Variablenwerte müssen durch die -Werte impliziert werden. Jedes -Bit wird durch eine bestimmte Menge der gesetzten impliziert . Beispiel: Unter der Annahme von Sie:$B$$X_{i,j}$$B_{i,*}$$X_{i,j}$$n = 16$

$ExactlyOne(X_{1,9}, X_{1,10}, X_{1,11}, X_{1,12}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,3}})$

erzwingt, dass wahr ist, wenn Taube 1 in eines der Löcher 9-16 gelegt wird. Andernfalls wird auf false gesetzt, um die Klausel zu erfüllen. Diese Klauseln setzen die verbleibenden Bits.$B_{1,3}$$B_{1,3}$$B_{i}$

$ExactlyOne(X_{1,5}, X_{1,6}, X_{1,7}, X_{1,8}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,2}})$ $ExactlyOne(X_{1,3}, X_{1,4}, X_{1,7}, X_{1,8}, X_{1,11}, X_{1,12}, X_{1,15}, X_{1,16}, \overline{B_{1,1}})$ $ExactlyOne(X_{1,2}, X_{1,4}, X_{1,6}, X_{1,8}, X_{1,10}, X_{1,12}, X_{1,14}, X_{1,16}, \overline{B_{1,0}})$

Für jede Taube wird ein dieser Klauseln erstellt. Da es Tauben gibt, werden -Klauseln hinzugefügt.$log(n)$$m$$m * log(n)$