{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:33:39Z","timestamp":1725492819973},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540420767"},{"type":"electronic","value":"9783540449928"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44992-2_13","type":"book-chapter","created":{"date-parts":[[2007,10,20]],"date-time":"2007-10-20T10:35:31Z","timestamp":1192876531000},"page":"199-208","source":"Crossref","is-referenced-by-count":7,"title":["A space-efficient randomized DNA algorithm for k-SAT"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Vijay","family":"Ramachandran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,4,25]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0166-218X(96)00058-3","volume":"71","author":"D. Boneh","year":"1996","unstructured":"D. Boneh, C. Dunworth, R. Lipton, and J. Sgall. On the computational power of DNA. Discrete Applied Mathematics: Special Issue on Computational Molecular Biology, 71:79\u201394, 1996.","journal-title":"Discrete Applied Mathematics: Special Issue on Computational Molecular Biology"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. Communications of the ACM, 5:394\u2013397, 1962.","journal-title":"Communications of the ACM"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis and H. Putnam. A computing procedure for quantification theory. Journal of the ACM, 7:201\u2013215, 1960.","journal-title":"Journal of the ACM"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1126\/science.7725098","volume":"268","author":"R. Lipton","year":"1995","unstructured":"R. Lipton. Using DNA to solve NP-complete problems. Science, 268:542\u2013545, April 1995.","journal-title":"Science"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"B. Monien and E. Speckenmeyer. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics, 10:287\u2013295, 1985.","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR6","volume-title":"Technical Report TR 629","author":"M. Ogihara","year":"1996","unstructured":"M. Ogihara. Breadth first search 3-SAT algorithms for DNA computers. Technical Report TR 629, University of Rochester, Department of Computer Science, Rochester, NY, July 1996."},{"key":"13_CR7","first-page":"628","volume-title":"39th Annual Symposium on Foundations of Computer Science","author":"R. Paturi","year":"1998","unstructured":"R. Paturi, P. Pudl\u00e1k, M. Saks, and F. Zane. An improved exponential-time algorithm for k-SAT. In 39th Annual Symposium on Foundations of Computer Science, pages 628\u2013637, Palo Alto, California, 8\u201311 Nov. 1998. IEEE."},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/SFCS.1997.646146","volume-title":"38th Annual Symposium on Foundations of Computer Science","author":"R. Paturi","year":"1997","unstructured":"R. Paturi, P. Pudl\u00e1k, and F. Zane. Satisfiability coding lemma. In 38th Annual Symposium on Foundations of Computer Science, pages 566\u2013574, Miami Beach, Florida, 20\u201322 Oct. 1997. IEEE."},{"key":"13_CR9","volume-title":"DNA Based Computers V","author":"H. Yoshida","year":"1999","unstructured":"H. Yoshida and A. Suyama. Solution to 3-SAT by breadth-first search. In E. Winfree and D. Gifford, editors, DNA Based Computers V, Cambridge, Massachusetts, 14\u201315 June 1999. American Mathematical Society."},{"key":"13_CR10","unstructured":"F. Zane. Circuits, CNFs, and Satisfiability. PhD thesis, University of California at San Diego, Department of Computer Science and Engineering, 1998."}],"container-title":["Lecture Notes in Computer Science","DNA Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44992-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T04:24:47Z","timestamp":1550982287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44992-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540420767","9783540449928"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-44992-2_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}