Solving the set-splitting problem in sticker-based model and the Adleman-Lipton model. (English) Zbl 1038.68046
Guo, Minyi (ed.) et al., Parallel and distributed processing and applications. International symposium, ISPA 2003, Aizu-Wakamatsu, Japan, July 2–4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40523-2/pbk). Lect. Notes Comput. Sci. 2745, 185-196 (2003).
Summary: Adleman wrote the first paper in which it was demonstrated that DNA (Deoxyriboa Nucleic Acid) strands could be applied for dealing with solutions to an instance of the NP-complete Hamiltonian path problem (HPP). Liton wrote the second paper in which it was shown that the Adleman techniques could also be used to solving 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 the paper, it is proved how to apply sticker in the sticker-based model for constructing the solution space of DNA for 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.
For the entire collection see [Zbl 1027.00029].
For the entire collection see [Zbl 1027.00029].
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 92D20 | Protein sequences, DNA sequences |
| 68W10 | Parallel algorithms in computer science |
