We present a general technique for proving NP-hardness (under randomized po
lynomial time reductions) of string folding problems over a finite alphabet
. All previous such intractability results have required an unbounded alpha
bet size. These problems correspond to the protein folding problem in varia
nts of the hydrophobic-hydrophilic (or HP) model with a fixed number of mon
omer types, Our proof also establishes the MAX SNP-hardness of these proble
ms (again under randomized polynomial time reductions), This means that obt
aining even an approximate solution to the protein folding problem, to with
in some fixed constant factor, is NP-hard, Our technique involves replacing
the symbols of an unbounded alphabet by codewords over a fixed alphabet, a
nd has two novel aspects, The first is the essential use of the approximati
on hardness of the source problem in the reduction, even for the proof of N
P-hardness, The second is the concept of spatial codes, a variant of classi
cal error-correcting codes in which different codewords are required to hav
e large "distance" from one another even when they are arbitrarily embedded
in three-dimensional space.