{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:18:07Z","timestamp":1772205487521,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T00:00:00Z","timestamp":1555891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            <jats:italic>Field-coupled Nanocomputing<\/jats:italic>\n            \u00a0(FCN) technologies provide an alternative to conventional CMOS-based computation technologies and are characterized by intriguingly low-energy dissipation. Accordingly, their design received significant attention in the recent past. FCN circuit implementations like\n            <jats:italic>Quantum-dot Cellular Automata<\/jats:italic>\n            \u00a0(QCA) or\n            <jats:italic>Nanomagnet Logic<\/jats:italic>\n            \u00a0(NML) have already been built in labs and basic operations such as inverters, Majority, AND, OR, and so on,\u00a0are already available. The design problem basically boils down to the question of how to place basic operations and route their connections so that the desired function results while, at the same time, further constraints (related to timing, clocking, path lengths, etc.) are satisfied. While several solutions for this problem have been proposed, interestingly no clear understanding about the complexity of the underlying task exists thus far. In this research note, we consider this problem and eventually prove that placement and routing for tile-based FCN circuits is\n            <jats:italic>NP<\/jats:italic>\n            -complete. By this, we provide a theoretical foundation for the further development of corresponding design methods.\n          <\/jats:p>","DOI":"10.1145\/3312661","type":"journal-article","created":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T15:24:23Z","timestamp":1556033063000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Placement and Routing for Tile-based Field-coupled Nanocomputing Circuits Is\n            <i>NP<\/i>\n            -complete (Research Note)"],"prefix":"10.1145","volume":"15","author":[{"given":"Marcel","family":"Walter","sequence":"first","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Gro\u00dfe","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank Sill","family":"Torres","sequence":"additional","affiliation":[{"name":"DFKI GmbH, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Drechsler","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43722-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1039\/C1NR10988J"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the CCCG. 295--299","author":"Biedl Therese C.","year":"1996","unstructured":"Therese C. Biedl . 1996 . Improved orthogonal drawings of 3-graphs . In Proceedings of the CCCG. 295--299 . Therese C. Biedl. 1996. Improved orthogonal drawings of 3-graphs. In Proceedings of the CCCG. 295--299."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2471996"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90030-7"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the TACAS\/ETAPS. 4.","author":"De Moura L.","unstructured":"L. De Moura and N. Bj\u00f8rner . 2008. Z3: An efficient SMT solver . In Proceedings of the TACAS\/ETAPS. 4. L. De Moura and N. Bj\u00f8rner. 2008. Z3: An efficient SMT solver. In Proceedings of the TACAS\/ETAPS. 4."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMAG.2012.2196030"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660540.2660997"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_1_10_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability\u2014A Guide to the Theory of NP-completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability\u2014A Guide to the Theory of NP-completeness. W. H. Freeman."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2018.2821107"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2016.2619377"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1116\/1.1394729"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1116696.1116697"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1021\/acsnano.7b04238"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211056"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10825-014-0590-z"},{"key":"e_1_2_1_18_1","volume-title":"Rivest","author":"LaPaugh Andrea S.","year":"1980","unstructured":"Andrea S. LaPaugh and Ronald L . Rivest . 1980 . The subgraph homeomorphism problem. J. Comput. Syst. Sci . (1980), 133--149. Andrea S. LaPaugh and Ronald L. Rivest. 1980. The subgraph homeomorphism problem. J. Comput. Syst. Sci. (1980), 133--149."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.573740"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.10.003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cds.2016.0252"},{"key":"e_1_2_1_23_1","volume-title":"A Proof Assistant for Higher-order Logic","author":"Nipkow Tobias","unstructured":"Tobias Nipkow , Lawrence C. Paulson , and Markus Wenzel . 2002. Isabelle\/HOL : A Proof Assistant for Higher-order Logic . Vol. 2283 . Springer Science 8 Business Media. Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. 2002. Isabelle\/HOL: A Proof Assistant for Higher-order Logic. Vol. 2283. Springer Science 8 Business Media."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2012.2220565"},{"key":"e_1_2_1_25_1","volume-title":"Nanomagnet Logic","author":"Porod Wolfgang","unstructured":"Wolfgang Porod , Gary H. Bernstein , Gy\u00f6rgy Csaba , Sharon X. Hu , Joseph Nahas , Michael T. Niemier , and Alexei Orlov . 2014. Nanomagnet Logic . Springer , Berlin , 21--32. Wolfgang Porod, Gary H. Bernstein, Gy\u00f6rgy Csaba, Sharon X. Hu, Joseph Nahas, Michael T. Niemier, and Alexei Orlov. 2014. Nanomagnet Logic. Springer, Berlin, 21--32."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the ISCAS.","author":"Reis D. A.","unstructured":"D. A. Reis , C. A. T. Campos , T. R. Soares , O. P. V. Neto , and F. S. Torres . 2016. A methodology for standard cell design for QCA . In Proceedings of the ISCAS. D. A. Reis, C. A. T. Campos, T. R. Soares, O. P. V. Neto, and F. S. Torres. 2016. A methodology for standard cell design for QCA. In Proceedings of the ISCAS."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mejo.2015.03.023"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2008.2005408"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1421217"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/NANO.2018.8626294"},{"key":"e_1_2_1_31_1","first-page":"12","article-title":"An energy-aware model for the logic synthesis of quantum-dot cellular automata","volume":"37","author":"Torres Frank Sill","year":"2018","unstructured":"Frank Sill Torres , Robert Wille , Philipp Niemann , and Rolf Drechsler . 2018 b. An energy-aware model for the logic synthesis of quantum-dot cellular automata . IEEE Trans. Comput.-Aided Design 37 , 12 (Dec. 2018), 3031--3041. Frank Sill Torres, Robert Wille, Philipp Niemann, and Rolf Drechsler. 2018b. An energy-aware model for the logic synthesis of quantum-dot cellular automata. IEEE Trans. Comput.-Aided Design 37, 12 (Dec. 2018), 3031--3041.","journal-title":"IEEE Trans. Comput.-Aided Design"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the DSD. 649--656","author":"Torres Frank Sill","year":"2018","unstructured":"Frank Sill Torres , Robert Wille , Marcel Walter , Philipp Niemann , Daniel Gro\u00dfe , and Rolf Drechsler . 2018 c. Evaluating the impact of interconnections in quantum-dot cellular automata . In Proceedings of the DSD. 649--656 . Frank Sill Torres, Robert Wille, Marcel Walter, Philipp Niemann, Daniel Gro\u00dfe, and Rolf Drechsler. 2018c. Evaluating the impact of interconnections in quantum-dot cellular automata. In Proceedings of the DSD. 649--656."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3145862.3145874"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907020"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMAG.2013.2249576"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.23919\/DATE.2018.8342060"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287624.3287705"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Robert A. Wolkow Lucian Livadaru etal 2014. Silicon Atomic Quantum Dots Enable Beyond-CMOS Electronics. Springer-Verlag 33--58.  Robert A. Wolkow Lucian Livadaru et al. 2014. Silicon Atomic Quantum Dots Enable Beyond-CMOS Electronics. Springer-Verlag 33--58.","DOI":"10.1007\/978-3-662-43722-3_3"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3312661","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3312661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:00Z","timestamp":1750208520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3312661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,22]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3312661"],"URL":"https:\/\/doi.org\/10.1145\/3312661","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,22]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}