INSTANCE:
Finite alphabet ,
finite string s from .
SOLUTION:
A folding of s in the 3-dimensional rectangular grid ,
that is, a mapping of s into
such that adjacent symbols
of s are adjacent in the lattice, and no site in the lattice is
occupied by more than one symbol.
MEASURE:
The number of pairs of equal symbols that lie at adjacent
lattice sites (excluding pairs that are adjacent in s).
Bad News:
APX-hard under randomized polynomial time reductions [385].
,
finite string s from 
.
,
that is, a mapping of s into