On the Power of DNA-Computing

Adleman 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 P^NP=Δ^p₂can 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,Δ^p₂, orΔ^p₃.