CaltechAUTHORS
  A Caltech Library Service

Whiplash PCR for O(1) Computing

Winfree, Erik (1998) Whiplash PCR for O(1) Computing. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1998.23

[img]
Preview
Postscript
See Usage Policy.

650Kb
[img]
Preview
PDF
See Usage Policy.

491Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1998.23

Abstract

This paper reviews the experimental technique of whiplash PCR, as introduced in Hagiya et al. (in press), and proposes a model of computation based on this technique in combination with assembly PCR (Stemmer et al. 1995). In this model, based on GOTO graphs, a number of NP-complete problems can be solved in O(1) biosteps, including branching program satisfiability, the independent set problem, and the Hamiltonian path problem. In addition, we propose a simple extension of the experimental technique that allows single DNA strands to simulate the execution of a feed-forward circuit, giving rise to a solution to the circuit satisfiability problem in O(1) biosteps.


Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1998.23
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1998.23
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:27061
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:16 Apr 2003
Last Modified:26 Dec 2012 14:13

Repository Staff Only: item control page