<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-298
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
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.
Download
cs-rr-298.ps.gz
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>