Sind Null-Eins-Puzzles NP-komplett?

18

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 × m{1n,1¯n¯}kk¯k{1n}m2m×m1×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 mnnnn=10101mund 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 kannT0000T0001T0011T0101T0111T1111T0000+T0001+T0011+T0101+T0111+T1111=m2mm) 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)

Steven Stadnicki
quelle
2
Es kann nicht NP-vollständig sein, da es nur mögliche Eingaben gibt, und nach Mahaneys Theorem brauchen Sie mehr als das, um ein Problem NP-vollständig zu machen (es sei denn, P = NP). Wenn Sie jedoch einen Rahmen verwenden, verschwindet dieses Hindernis. Es könnte also NP-komplett mit einem Rahmen sein. θ(m10)
Peter Shor
1
Ein Zwischenschritt wäre zu beweisen, dass das Problem, zu entscheiden, ob ein teilweise gefülltes 6-Kacheln-Puzzle (dh einige der Teile sind bereits auf dem Brett und können nicht bewegt werden) korrekt abgeschlossen werden kann, NP-vollständig ist.
Vor dem

Antworten:

3

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

DW
quelle
Ich stimme zu, dass dies ein vernünftiges Mittel zur Lösung des Problems zu sein scheint , aber ich bin weniger an der gezielten Lösung von Instanzen des Problems interessiert, als vielmehr am Verständnis seiner Komplexität. (Zum Beispiel, wenn es in P ist, dann gibt es mit ziemlicher Sicherheit eine Art dynamischer Programmieransatz, der abstrakte SAT / lineare Programmierlöser in Bezug auf das Problem übertreffen würde.)
Steven Stadnicki
@StevenStadnicki, OK, fair genug. Ich bemühe mich jedoch, ~ "Ich bin daran interessiert, seine (asymptotische) Komplexität zu verstehen (z. B. ob es NP-vollständig ist)" ~ mit ~ "Ich interessiere mich für das Problem für kleine Werte von " ~ . n
DW
Entschuldigung, dies kann zu Verwirrung in der Problembeschreibung führen. Ich benutze , um (im Wesentlichen) die Anzahl der Kantenformen zu bezeichnen, und ich interessiere mich besonders für den Fall, dass es nur eine passende Kantenform gibt (denken Sie an 'innie' oder 'outie'). Ich wundere mich über die Komplexität dieses Problems als Funktion von , der Gittergröße. mnm
Steven Stadnicki
@StevenStadnicki, ahh, mein Fehler! Entschuldigung, ich habe nicht sorgfältig genug gelesen. Das macht Sinn - danke.
DW
Keine Sorge - ich hätte es mir von vornherein überlegen sollen; Wenn ich nach Hause komme, werde ich versuchen, die Frage zu bearbeiten, um eine "traditionellere" Parametrisierung zu verwenden.
Steven Stadnicki