# Complexity of $n \times \log n$ tiling problem

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$?

• What did you try? Where did you get stuck? – 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)$.)