  We study the complexity of a class of problems involving satisfying
constraints which remain the same under translations in one or more spatial
directions. In this paper, we show hardness of a classical tiling problem on an
N x N 2-dimensional grid and a quantum problem involving finding the ground
state energy of a 1-dimensional quantum system of N particles. In both cases,
the only input is N, provided in binary. We show that the classical problem is
NEXP-complete and the quantum problem is QMA_EXP-complete. Thus, an algorithm
for these problems which runs in time polynomial in N (exponential in the input
size) would imply that EXP = NEXP or BQEXP = QMA_EXP, respectively. Although
tiling in general is already known to be NEXP-complete, to our knowledge, all
previous reductions require that either the set of tiles and their constraints
or some varying boundary conditions be given as part of the input. In the
problem considered here, these are fixed, constant-sized parameters of the
problem. Instead, the problem instance is encoded solely in the size of the
system.
