On the Power of DNA-Computing

AbstractAdleman used biological manipulations with DNA strings to solve some instances of the Directed Hamiltonian Path Problem. Lipton showed how to extend this idea to solve any NP problem. We prove that exactly the problems in PNP=Δp2can be solved in polynomial time using Lipton's model. Various modifications of Lipton's model, based on other DNA manipulations, are investigated systematically, and it is proved that their computational power in polynomial time can be characterized by one of the complexity classes P,Δp2, orΔp3