A Caltech Library Service

Whiplash PCR for O(1) Computing

Winfree, Erik (1998) Whiplash PCR for O(1) Computing. California Institute of Technology , Pasadena, CA. (Unpublished)

Postscript - Submitted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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)
Winfree, Erik0000-0002-5899-7523
Additional Information:© 1998 California Institute of Technology.
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1998.23
Persistent URL:
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
Deposited By: Imported from CaltechCSTR
Deposited On:16 Apr 2003
Last Modified:03 Oct 2019 03:20

Repository Staff Only: item control page