Spatial codes and the hardness of string folding problems

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.