Sind Null-Eins-Puzzles NP-komplett?

Ich interessiere mich für eine kleine Variante des Kachelns, das "Puzzle": Jede Kante eines (quadratischen) Kachels ist mit einem Symbol aus und zwei Kacheln können nebeneinander platziert werden, wenn das Symbol an der gegenüberliegenden Kante einer Kachel und das Symbol an der gegenüberliegenden Kante der anderen Kachel , für einige . Können sie dann bei einer Menge von Kacheln in einem Quadrat von (die Kacheln drehen, aber nicht spiegeln), wobei alle Kanten korrekt übereinstimmen? (Es gibt auch eine Variante zu diesem Problem, bei der vier -Rahmenkanten vorgesehen sind und die Teile korrekt in diesen Rahmen passen müssen.)k ≤ k k ≤ { 1 … n } m 2 m × m 1 × $\{1\ldots n, \bar{1}\ldots\bar{n}\}$$k$$\bar{k}$$k\in\{1\ldots n\}$$m^2$$m\times m$$1\times m$

Ich weiß, dass dieses Problem für ausreichend große NP-vollständig ist , aber die Grenzen, die ich für gesehen habe, scheinen ziemlich groß zu sein; Ich interessiere mich für das Problem für kleine Werte von und insbesondere für , den 'Null-Eins'-Fall (bei dem jede Kante entweder mit oder und Kanten mit einer mit Kanten mit einer abgeglichen werden müssen ). Hier gibt es (mit Rotationssymmetrie) nur sechs Kacheltypen (die Kachel mit allen Nullen, die Kachel mit allen Einsen, die Kachel mit drei Nullen und einer Eins, die Kachel mit drei Einsen und einer Null und zwei unterschiedliche Kacheln mit zwei Nullen und zwei, '0011' und '0101'), so dass eine Probleminstanz nur eine Angabe vonn n n = 1 0 1 0 1 m T 0000 T 0001 T 0011 T 0101 T 0111 T 1111 T 0000 + T 0001 + T 0011 + T 0101 + T 0111 + T 1111 = m 2 m $n$$n$$n$$n=1$$0$$1$$0$$1$$m$und einen Satz von fünf Zahlen , , , , und (die die Zählung jedes Kacheltyps darstellen) mit . Das Problem liegt offensichtlich in NP (wobei in unary angegeben ist), da eine Lösung einfach gezeigt und dann in Polynom (in überprüft werden kann$T_{0000}$$T_{0001}$$T_{0011}$$T_{0101}$$T_{0111}$$T_{1111}$$T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$$m$$m$) Zeit, aber ist bekannt, dass es NP-vollständig ist, oder gibt es einen dynamischen Programmieralgorithmus, der hier angewendet werden kann? Was ist mit dem "gerahmten" Fall, in dem die Problemspezifikation auch die vier Kanten des Quadrats enthält, die abgeglichen werden sollen? (Offensichtlich, wenn der ungerahmte Fall NP-vollständig ist, ist der gerahmte Fall mit ziemlicher Sicherheit auch so)

Da Sie erwähnt haben, dass Sie daran interessiert sind, dieses Problem für kleine Werte von lösen , würde ich vorschlagen, dass Sie versuchen, dies in einem SAT-Löser oder als ganzzahliges lineares Programm (ILP) zu implementieren. Entweder kann man die Bedingungen codieren, aber auf eine etwas andere Weise:$n$

• Für SAT gibt es eine sehr saubere Kodierung der Auswahl, welche Kachel in jedes Quadrat eingeht, und eine etwas weniger saubere Kodierung der Beschränkung hinsichtlich der Anzahl jeder Kachelart (unter Verwendung von Bit-Arithmetik).

• Für ILP gibt es eine sehr saubere Codierung der Einschränkung in Bezug auf die Anzahl der verfügbaren Kacheltypen und eine etwas weniger saubere Codierung der Einschränkungen, bei denen Kacheln nebeneinander liegen können (was Sie aber immer noch ausdrücken können) beliebige boolesche Formeln in ILP ausdrücken).

Ich würde erwarten, dass dieser Ansatz für kleine oder mittlere effizient funktionieren könnte.$n$