Treffer: A ROBUST DNA COMPUTATION MODEL THAT CAPTURES PSPACE.

One of the most serious problems in DNA computing is that basic DNA operations are faulty. Many DNA computation models use operations based on annealing and magnetic-beads separation which sometimes produce undesirable results. Some models use reliable operations only but their computational power is too weak. The purpose of this paper is to find a good trade-off between the robustness of DNA operations and their computational power. We present a robust DNA computation model that can solve computationally hard problems. We prove that (i) this model can solve PSPACE-complete problems, and (ii) any computational problem that can be solved with this model is in PSPACE. [ABSTRACT FROM AUTHOR]

Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)