Name
Abstract | ||
|---|---|---|
Abstract We present,the first proof of NP-hardness,(under randomized polynomial,time,reductions),for string folding,problems over a finite alphabet. All previous,such intractability results have,required,an unbounded,alphabet,size. These problems,correspond,to the protein,folding problem,in variants of the hydrophobic-hydrophilic,(or HP) model,with a fixed number,of monomer,types. Our proof also establishes the MAX,SNP-hardness of the problem,(again under randomized polynomial time reductions). This means,that ob tailing even,an approximate,solution,to the protein,folding problem, to within some fixed constant, is NP-hard. Our results are based,on a general,technique,for replacing unbounded,alphabets,by finite alphabets,in reductions,for string folding problems.,This technique,has,two novel aspects. The first is the essential use of the approximation hardness of the source problem in the reduction, even for the proof,of NP-hardness. The second,is the concept,of spatial codes, a variant of cla.&ical error-correcting codes in which different codewords are required to have,large,“distance”,from one another even when they are arbitrarily embedded,in three-dimensional,space. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1145/314613.315034 | SODA |
Keywords | Field | DocType |
three dimensional,protein folding,error correction code | Discrete mathematics,Combinatorics,Computer science | Conference |
Citations | PageRank | References |
1 | 0.35 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashwin Nayak | 1 | 645 | 61.76 |
| Alistair Sinclair | 2 | 1506 | 308.40 |
| Uri Zwick | 3 | 3586 | 257.02 |