A Space-Efficient Randomized DNA Algorithm for k-SAT

Kevin Chen and Vijay Ramachandran

Abstract

We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. For an n-variable, m-clause instance of k-SAT (m > n), our algorithm finds a satisfying assignment, assuming one exists, with probability $1-e^{-\alpha}$, in worst-case time $O(k^2 m n)$ and space $O(2^{(1-1/k)n + \log \alpha})$. This makes it the most space-efficient DNA k-SAT algorithm for 3 < k < $n / \log \alpha$ (i.e., the clause size is small compared to the number of variables). In addition, our algorithm is the first DNA algorithm to adapt techniques from the field of randomized classical algorithms.

Current Citation

K. Chen and V. Ramachandran. "A Space-Efficient Randomized DNA Algorithm for k-SAT." In Proc. DNA6, LNCS vol. 2054, pp. 199-208, June 2000.

@inproceedings{cr00-dna-ksat,
	title = {A Space-Efficient Randomized {DNA} Algorithm for $k$-{SAT}},
	author = {Kevin Chen and Vijay Ramachandran},
	booktitle = {Proc. {DNA}6}
	year = {2000},
	month = {June},
	pages = {199--208},
	series = {LNCS}
	volume = {2054},
	publisher = {Springer} }

Download
(in reverse chronological order)

Filetype	Version
(146K)	Conference-proceedings version (June 2000).
(182K)	Revised set of slides from conference talk.