What is the complexity of the pallet loading problem?
Given two pairs of numbers, (A, B) and (a, b), and a number n,
decide whether n small rectangles of size
a×b,
in either axis-parallel orientation,
can be packed into a large rectangle of size
A×B.
This problem is not even known to be in NP, because of the compact
input description, and the possibly complicated structure
of a packing, if there is one.