Whiplash PCR for O(1) Computing

Winfree, Erik (1998) Whiplash PCR for O(1) Computing. Technical Report. California Institute of Technology. [CaltechCSTR:1998.23]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	PDF - Requires Adobe Acrobat Reader or other PDF viewer.

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.

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	484
Deposited By:	INVALID USER
Deposited On:	16 April 2003
Record Number:	CaltechCSTR:1998.23
Official 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.

Archive Staff Only: edit this record