Small polyomino packing

The problem of tiling a rectangle by polyominoes is known to be NP-complete if the polyominoes used are polylogarithmic in size. On the other hand, if the same is true for polyominoes of sub-logarithmic size, this would imply P=NP. This paper closes the gap between logarithmic and polylogarithmic-sized pieces by proving that tiling remains NP-complete even when only pieces of logarithmic area are used. Equivalently, we show that the problem of “small polyomino packing”, this being the packing problem where the polyominoes used are the n smallest polyominoes and the inputs are their multiplicities, is strongly NP-complete.