Small polyomino packing

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.