This paper studies seemingly the smallest DNA computational model. This model assumes as its computation basis merge, detect, synthesize, anneal, and length-specific separation, but does not assume sequence-specific separation as in many other DNA computational models. Uncertainty occurring in some of the operations is taken into consideration, and the decision by computation under the model is defined in terms of robustness. This paper shows tight upper bounds on the power of this computational model in terms of circuits. For every k >= 1, the languages robustly accepted by programs under this model in O (log~k, n) steps using polynomially many DNA molecules resides between NC~k and SAC~(k+1).
展开▼
