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 AdlemanLipton 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 AdlemanLipton model to solve that problem from the solution space of sticker.
biological computing molecular computing dna-based computing the np-complete problem