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