A space-effcient randomized DNA algorithm for k-SAT

Kevin Chen; Vijay Ramachandran

doi:10.1007/3-540-44992-2_13

A space-effcient randomized DNA algorithm for k-SAT

Kevin Chen, Vijay Ramachandran

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. [8]. 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^−α, in worst-case time O(k²mn) and space (Formula Presented). This makes it the most space-eficient DNA k-SAT algorithm for k > 3 and k < n=log α (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.

Original language	English (US)
Title of host publication	DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers
Editors	Grzegorz Rozenberg, Anne Condon
Publisher	Springer Verlag
Pages	199-208
Number of pages	10
ISBN (Print)	3540420762, 9783540420767
DOIs	https://doi.org/10.1007/3-540-44992-2_13
State	Published - 2001
Externally published	Yes
Event	6th International Workshop on DNA-Based Computers, DNA 2000 - Leiden, Netherlands Duration: Jun 13 2000 → Jun 17 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2054
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th International Workshop on DNA-Based Computers, DNA 2000
Country/Territory	Netherlands
City	Leiden
Period	6/13/00 → 6/17/00

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44992-2_13

Cite this

Chen, K., & Ramachandran, V. (2001). A space-effcient randomized DNA algorithm for k-SAT. In G. Rozenberg, & A. Condon (Eds.), DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers (pp. 199-208). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2054). Springer Verlag. https://doi.org/10.1007/3-540-44992-2_13

Chen, Kevin ; Ramachandran, Vijay. / A space-effcient randomized DNA algorithm for k-SAT. DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. editor / Grzegorz Rozenberg ; Anne Condon. Springer Verlag, 2001. pp. 199-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6a41b68d92104436aff102c89885f939,

title = "A space-effcient randomized DNA algorithm for k-SAT",

abstract = "We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. [8]. 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−α, in worst-case time O(k2mn) and space (Formula Presented). This makes it the most space-eficient DNA k-SAT algorithm for k > 3 and k < n=log α (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.",

author = "Kevin Chen and Vijay Ramachandran",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 6th International Workshop on DNA-Based Computers, DNA 2000 ; Conference date: 13-06-2000 Through 17-06-2000",

year = "2001",

doi = "10.1007/3-540-44992-2_13",

language = "English (US)",

isbn = "3540420762",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "199--208",

editor = "Grzegorz Rozenberg and Anne Condon",

booktitle = "DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers",

address = "Germany",

}

Chen, K & Ramachandran, V 2001, A space-effcient randomized DNA algorithm for k-SAT. in G Rozenberg & A Condon (eds), DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2054, Springer Verlag, pp. 199-208, 6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, Netherlands, 6/13/00. https://doi.org/10.1007/3-540-44992-2_13

A space-effcient randomized DNA algorithm for k-SAT. / Chen, Kevin; Ramachandran, Vijay.
DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. ed. / Grzegorz Rozenberg; Anne Condon. Springer Verlag, 2001. p. 199-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2054).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A space-effcient randomized DNA algorithm for k-SAT

AU - Chen, Kevin

AU - Ramachandran, Vijay

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. [8]. 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−α, in worst-case time O(k2mn) and space (Formula Presented). This makes it the most space-eficient DNA k-SAT algorithm for k > 3 and k < n=log α (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.

AB - We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. [8]. 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−α, in worst-case time O(k2mn) and space (Formula Presented). This makes it the most space-eficient DNA k-SAT algorithm for k > 3 and k < n=log α (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.

UR - http://www.scopus.com/inward/record.url?scp=84958954148&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958954148&partnerID=8YFLogxK

U2 - 10.1007/3-540-44992-2_13

DO - 10.1007/3-540-44992-2_13

M3 - Conference contribution

AN - SCOPUS:84958954148

SN - 3540420762

SN - 9783540420767

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 199

EP - 208

BT - DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers

A2 - Rozenberg, Grzegorz

A2 - Condon, Anne

PB - Springer Verlag

T2 - 6th International Workshop on DNA-Based Computers, DNA 2000

Y2 - 13 June 2000 through 17 June 2000

ER -

Chen K, Ramachandran V. A space-effcient randomized DNA algorithm for k-SAT. In Rozenberg G, Condon A, editors, DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. Springer Verlag. 2001. p. 199-208. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44992-2_13

A space-effcient randomized DNA algorithm for k-SAT

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this