Research Report CS-RR-298
M. Amos, A.M. Gibbons and D. Hodgson, Error-resistant Implementation of DNA Computations (January 1, 1996).
Abstract
This paper introduces a new model of computation that employs the tools of molecular biology whose in vitro implementation is far more error-resistant than extant proposals. We describe an abstraction of the model which lends itself to natural algorithmic description, particularly for problems in the complexity class NP. In addition we describe a number of linear-time algorithms within our model, particularly for NP-complete problems. We describe an in vitro realisation of the model and conclude with a discussion of future work.