DNA Models and Algorithms for NP-Complete Problems

✍ Scribed by Eric Bach; Anne Condon; Elton Glaser; Celena Tanguay

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 488 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1586

✦ Synopsis

A goal of research on DNA computing is to solve problems that are beyond the capabilities of the fastest silicon-based supercomputers. Adleman and Lipton present exhaustive search algorithms for 3Sat and 3-coloring, which can only be run on small instances and, hence, are not practical. In this paper, we show how improved algorithms can be developed for the 3-coloring and independent set problems. Our algorithms use only the DNA operations proposed by Adleman and Lipton, but combine them in more powerful ways and use polynomial preprocessing on a standard computer to tailor them to the specific instance to be solved. The main contribution of this paper is a more general model of DNA algorithms than that proposed by Lipton. We show that DNA computation for NP-complete problems can do more than just exhaustive search. Further research in this direction will help determine whether or not DNA computing is viable for NP-hard problems. A second contribution is the first analysis of errors that arise in generating the solution space for DNA computation.