Czy układanki „zero-jedynkowe” są kompletne NP?

18

Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka to ˉ k , dla niektórych k { 1 n } . Następnie, biorąc pod uwagę zestaw m 2 płytek, można je umieścić w m × m{1n,1¯n¯}kk¯k{1n}m2m×mkwadratowy (obracający się, ale nie odwracający płytki) z dopasowaniem wszystkich krawędzi? (Istnieje również wariant tego problemu, w którym cztery 1×m krawędzie kadrowania o a elementy muszą dobrze pasować do tej ramy).

Wiem, że ten problem jest NP-zupełny dla wystarczająco dużego , ale granice, które widziałem na n, wydają się być dość duże; Interesuje mnie problem małych wartości n, a zwłaszcza n = 1 , przypadek „zero-jeden” (gdzie każda krawędź jest oznaczona jako 0 lub 1, a krawędzie z 0 muszą być dopasowane do krawędzi z 1nnnn=10101mT0000T0001T0011T0101T0111T1111T0000+T0001+T0011+T0101+T0111+T1111=m2mm) time, but is it known to be NP-complete, or is there some dynamic programming algorithm that can be applied here? What about the 'framed' case where the problem specification also includes the four edges of the square that are to be matched? (Obviously if the unframed case is NP-complete the framed case almost certainly is as well)

Steven Stadnicki
źródło
2
It can't be NP-complete, since there are only θ(m10) possible inputs, and by Mahaney's theorem you need more than that to make a problem NP-complete (unless P=NP). But if you use a frame, this obstruction vanishes. So it might be NP-complete with a frame.
Peter Shor
1
An intermediate step would be to prove that the problem of deciding if a partially filled 6-tiles jigsaw puzzle (i.e. some of the pieces are already on the board and cannot be moved) can be correctly completed is NP-complete.
Vor

Odpowiedzi:

3

Since you mentioned you are interested in solving this problem for small values of n, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP). Either one will be able to encode the constraints, but in a slightly different way:

  • For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).

  • For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).

I would expect that for small or medium sized n, this approach might work efficiently.

D.W.
źródło
Zgadzam się, że wydaje się to rozsądnym sposobem rozwiązania problemu, ale mniej interesuje mnie konkretne rozwiązywanie problemów niż zrozumienie jego złożoności. (Na przykład, jeśli jest to w P potem jest prawie na pewno jakiś rodzaj dynamicznego programowania podejścia do niej, że dłoń prześcigają abstrakcyjnych TV / liniowe rozwiązują programowania na problemie.)
Steven Stadnicki
@StevenStadnicki, OK, wystarczy. Jednak staram się pogodzić ~ "Jestem zainteresowany zrozumieniem jego (asymptotycznej) złożoności (np. Czy jest to NP-zupełny)" ~ z ~ "Jestem zainteresowany problemem dla małych wartościn"~.
D.W.
Sorry, that may be some confusion in the problem specification; I'm using n to denote (essentially) the number of edge shapes and I'm particularly interested in the case where there's only one edge shape to match (think 'innie' or 'outie'); I'm wondering about the complexity of that problem as a function of m, the grid size.
Steven Stadnicki
@StevenStadnicki, ahh, my mistake! Sorry, I didn't read carefully enough. That makes sense -- thank you.
D.W.
No worries - I should have considered it up front; when I get home I'll try and edit the question to use a more 'traditional' parametrization.
Steven Stadnicki