Math Forum

From: haoyuep@aol.com (Dan Hoey)
Date: Jul 4, 2002 9:41 PM
Subject: Re: complexity of pentominoe-like tiling problems

David Bernier asks:

> How complex is the decision problem for tiling-problems using a
> finite (irregularly-shaped) set or collection of pieces cut-out
> from a square-grid along horizontal and vertical grid lines?

and proposes an answer based on the SET PARTITION problem (a close
relative to KNAPSACK).  The problem is that these problems are not
NP-hard in the "strong sense".  That is, the problem is solvable in
time polynomial in the sum of the numbers involved (rather than the
sum of their logarithms, in which the time is exponential).

But tiling problems are typically represented in size proportional to
the number of squares to be tiled, since instances are not restricted
to the simple shapes that can be represented logarithmically.  So in
the usual sense, the example given is solvable in polynomial time.
For a better construction, see "Hard Tiling Problems with Simple
Tiles" by Cristopher Moore and John Michael Robson, at
http://arxiv.org/abs/math.CO/0003039 .

The abstract begins:

  It is well-known that the question of whether a given finite region
  can be tiled with a given set of tiles is NP-complete.  We show that
  the same is true for the right tromino and square tetromino on the
  square lattice, or for the right tromino alone....

but even if you didn't know the result well in the first place,
their construction will be enlightening.

Dan Hoey
haoyuep@aol.com