- 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].