{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:27:07Z","timestamp":1725823627277},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_83","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"1022-1034","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Binary Pattern Tile Set Synthesis Is NP-hard"],"prefix":"10.1007","author":[{"given":"Lila","family":"Kari","sequence":"first","affiliation":[]},{"given":"Steffen","family":"Kopecki","sequence":"additional","affiliation":[]},{"given":"Pierre-\u00c9tienne","family":"Meunier","sequence":"additional","affiliation":[]},{"given":"Matthew J.","family":"Patitz","sequence":"additional","affiliation":[]},{"given":"Shinnosuke","family":"Seki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"3","key":"83_CR1","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1706591.1706594","volume":"57","author":"E Allender","year":"2010","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. J. ACM 57(3), 14:1\u201314:36 (2010)","journal-title":"J. ACM"},{"key":"83_CR2","first-page":"429","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. Part I. discharging. Illinois J. Math. 21, 429\u2013490 (1977)","journal-title":"Part I. discharging. Illinois J. Math."},{"key":"83_CR3","first-page":"491","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. Part II. reducibility. Illinois J. Math. 21, 491\u2013567 (1977)","journal-title":"Part II. reducibility. Illinois J. Math."},{"issue":"12","key":"83_CR4","doi-asserted-by":"publisher","first-page":"2586","DOI":"10.1021\/nl052038l","volume":"5","author":"R Barish","year":"2005","unstructured":"Barish, R., Rothemund, P.W.K., Winfree, E.: Two computational primitives for algorithmic self-assembly: Copying and counting. Nano. Lett. 5(12), 2586\u20132592 (2005)","journal-title":"Nano. Lett."},{"issue":"4","key":"83_CR5","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1016\/j.jcss.2010.06.017","volume":"77","author":"TY Chow","year":"2011","unstructured":"Chow, T.Y.: Almost-natural proofs. J. Comput. Syst. Sci. 77(4), 728\u2013737 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"83_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-540-24628-2_11","volume-title":"DNA Computing","author":"M Cook","year":"2004","unstructured":"Cook, M., Rothemund, P.W.K., Winfree, E.: Self-assembled circuit patterns. In: Chen, J., Reif, J.H. (eds.) DNA 2003. LNCS, vol. 2943, pp. 91\u2013107. Springer, Heidelberg (2004)"},{"key":"83_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2013.05.009","volume":"499","author":"E Czeizler","year":"2013","unstructured":"Czeizler, E., Popa, A.: Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. Theor. Comput. Sci. 499, 23\u201337 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"83_CR8","first-page":"1382","volume":"55","author":"G Gonthier","year":"2008","unstructured":"Gonthier, G.: Formal proof - the four-color theorem. Not. Am. Math. Soc. 55(11), 1382\u20131393 (2008)","journal-title":"Not. Am. Math. Soc."},{"key":"83_CR9","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.jcss.2013.08.003","volume":"80","author":"M G\u00f6\u00f6s","year":"2014","unstructured":"G\u00f6\u00f6s, M., Lempi\u00e4inen, T., Czeizler, E., Orponen, P.: Search methods for tile sets in patterned DNA self-assembly. J. Comput. Syst. Sci. 80, 297\u2013319 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"83_CR10","unstructured":"Helfgott, H.A.: The ternary Goldbach conjecture is true arXiv:1312.7748 (2013)"},{"key":"83_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/978-3-642-45030-3_65","volume-title":"Algorithms and Computation","author":"AC Johnsen","year":"2013","unstructured":"Johnsen, A.C., Kao, M.-Y., Seki, S.: Computing minimum tile sets to self-assemble color patterns. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 699\u2013710. Springer, Heidelberg (2013)"},{"key":"83_CR12","doi-asserted-by":"crossref","unstructured":"Johnsen, A., Kao, M.Y., Seki, S.: A manually-checkable proof for the NP-hardness of 11-colored patterned self-assembly of tile set synthesis. arXiv:1409.1619 (2014)","DOI":"10.1007\/s10878-015-9975-6"},{"key":"83_CR13","doi-asserted-by":"crossref","unstructured":"Kari, L., Kopecki, S., Meunier, P.E., Patitz, M.J., Seki, S.: Binary pattern tile set synthesis is NP-hard. arXiv:1404.0967 (2014)","DOI":"10.1007\/978-3-662-47672-7_83"},{"key":"83_CR14","doi-asserted-by":"crossref","unstructured":"Kari, L., Kopecki, S., Seki, S.: 3-color bounded patterned self-assembly. Nat. Comp. (2014) (in Press)","DOI":"10.1007\/978-3-319-01928-4_8"},{"key":"83_CR15","doi-asserted-by":"crossref","unstructured":"Konev, B., Lisitsa, A.: A SAT attack on the Erd\u00f6s discrepancy conjecture. arXiv: 1402.2184 (2014)","DOI":"10.1007\/978-3-319-09284-3_17"},{"key":"83_CR16","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1038\/nature09012","volume":"465","author":"K Lund","year":"2010","unstructured":"Lund, K., Manzo, A.T., Dabby, N., Micholotti, N., Johnson-Buck, A., Nangreave, J., Taylor, S., Pei, R., Stojanovic, M.N., Walter, N.G., Winfree, E., Yan, H.: Molecular robots guided by prescriptive landscapes. Nature 465, 206\u2013210 (2010)","journal-title":"Nature"},{"issue":"5","key":"83_CR17","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1109\/TCAD.2008.917973","volume":"27","author":"X Ma","year":"2008","unstructured":"Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE T. Comput. Aid. D. 27(5), 963\u2013967 (2008)","journal-title":"IEEE T. Comput. Aid. D."},{"key":"83_CR18","doi-asserted-by":"crossref","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), Article No. 11 (2008)","DOI":"10.1145\/1346330.1346336"},{"issue":"6034","key":"83_CR19","doi-asserted-by":"publisher","first-page":"1196","DOI":"10.1126\/science.1200520","volume":"332","author":"L Qian","year":"2011","unstructured":"Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034), 1196 (2011)","journal-title":"Science"},{"key":"83_CR20","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: Proc. STOC 1994, pp. 204\u2013213. ACM, New York (1994)","DOI":"10.1145\/195058.195134"},{"issue":"1","key":"83_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1090\/S1079-6762-96-00003-0","volume":"2","author":"N Robertson","year":"1996","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: A new proof of the four-colour theorem. Electron. Res. Announc. AMS. 2(1), 17\u201325 (1996)","journal-title":"Electron. Res. Announc. AMS."},{"issue":"12","key":"83_CR22","doi-asserted-by":"publisher","first-page":"2041","DOI":"10.1371\/journal.pbio.0020424","volume":"2","author":"PW Rothemund","year":"2004","unstructured":"Rothemund, P.W., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2(12), 2041\u20132053 (2004)","journal-title":"PLoS Biol."},{"key":"83_CR23","first-page":"204","volume":"55","author":"S Rudich","year":"1997","unstructured":"Rudich, S.: Super-bits, demi-bits, and NP\/qpoly-natural proofs. J. Comput. Syst. Sci. 55, 204\u2013213 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5805","key":"83_CR24","doi-asserted-by":"publisher","first-page":"1585","DOI":"10.1126\/science.1132493","volume":"314","author":"G Seelig","year":"2006","unstructured":"Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585\u20131588 (2006)","journal-title":"Science"},{"key":"83_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0022-5193(82)90002-9","volume":"99","author":"NC Seeman","year":"1982","unstructured":"Seeman, N.C.: Nucleic-acid junctions and lattices. J. Theor. Biol. 99, 237\u2013247 (1982)","journal-title":"J. Theor. Biol."},{"key":"83_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-642-39074-6_21","volume-title":"Unconventional Computation and Natural Computation","author":"S Seki","year":"2013","unstructured":"Seki, S.: Combinatorial optimization in pattern assembly. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 220\u2013231. Springer, Heidelberg (2013)"},{"key":"83_CR27","unstructured":"Sterling, A.: https:\/\/nanoexplanations.wordpress.com\/2011\/08\/13\/dna-self-assembly-of-multicolored-rectangles\/"},{"key":"83_CR28","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1073\/pnas.68.10.2319","volume":"68","author":"B Tuckerman","year":"1971","unstructured":"Tuckerman, B.: The 24th Mersenne prime. Proc. Nat. Acad. Sci. USA 68, 2319\u20132320 (1971)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"83_CR29","doi-asserted-by":"crossref","unstructured":"Wang, H.: Proving theorems by pattern recognition - II. AT&T Tech. J. XL(1), 1\u201341 (1961)","DOI":"10.1002\/j.1538-7305.1961.tb03975.x"},{"key":"83_CR30","unstructured":"Winfree, E.: Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998"},{"key":"83_CR31","doi-asserted-by":"publisher","first-page":"1882","DOI":"10.1126\/science.1089389","volume":"301","author":"H Yan","year":"2003","unstructured":"Yan, H., Park, S.H., Finkelson, G., Reif, J.H., LaBean, T.H.: DNA-templated self-assembly of protein arrays and highly conductive nanowires. Science 301, 1882\u20131884 (2003)","journal-title":"Science"},{"issue":"6796","key":"83_CR32","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1038\/35020524","volume":"406","author":"B Yurke","year":"2000","unstructured":"Yurke, B., Turberfield, A.J., Mills, A.P., Simmel, F.C., Neumann, J.L.: A DNA-fuelled molecular machine made of DNA. Nature 406(6796), 605\u2013608 (2000)","journal-title":"Nature"},{"issue":"2","key":"83_CR33","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1021\/nl052210l","volume":"6","author":"J Zhang","year":"2006","unstructured":"Zhang, J., Liu, Y., Ke, Y., Yan, H.: Periodic square-like gold nanoparticle arrays templated by self-assembled 2D DNA nanogrids on a surface. Nano Letters 6(2), 248\u2013251 (2006)","journal-title":"Nano Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_83","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:15:48Z","timestamp":1676945748000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_83","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}