Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?

For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a matrix of tiles in which any adjacent symbols (including diagonally) in neighboring tiles are equal.

The Tiling Problem is as follows. Given a set of tiles $T$ and a sequence $C_1$ of $\log n$ tiles from $T$, is there an $n \times \log n$ tiling of $T$ whose first row is $C_1$?

  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Mar 18 '16 at 17:05

Hint: Use dynamic programming, going row by row. Use the fact that there are only $\log n$ many columns, and so only $|A|^{\log n} = n^{\log |A|}$ many different configurations of each column.

(The resulting algorithm will be polynomial in $n$ but not in the input size, which is only $O(\log n)$.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.