Towards solution of the set-splitting problem on gel-based DNA computing

摘要

Adleman wrote the first paper that demonstrated that DNA (DeoxyriboNucleic Acid) strands could be applied for dealing with solutions of the NP-complete Hamiltonian path problem (HPP). Lipton wrote the second paper that showed that the Adleman techniques could also be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem). Adleman and his co-authors proposed sticker for enhancing the Adleman-Lipton model. In this paper, it proves how to apply sticker in the sticker-based model to construct solution space of DNA in the set-splitting problem and how to apply DNA operations in the Adleman-Lipton model to solve that problem from the solution space of sticker.