{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T11:46:58Z","timestamp":1777290418863,"version":"3.51.4"},"reference-count":48,"publisher":"Wiley","issue":"12","license":[{"start":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T00:00:00Z","timestamp":1664668800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["732482"],"award-info":[{"award-number":["732482"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003252","name":"Lund University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003252","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["advanced.onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Advanced Intelligent Systems"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:sec><jats:label\/><jats:p>The 3\u2010satisfiability Problem (3\u2010SAT) is a demanding combinatorial problem that is of central importance among the nondeterministic polynomial (NP) complete problems, with applications in circuit design, artificial intelligence, and logistics. Even with optimized algorithms, the solution space that needs to be explored grows exponentially with the increasing size of 3\u2010SAT instances. Thus, large 3\u2010SAT instances require excessive amounts of energy to solve with serial electronic computers. Network\u2010based biocomputation (NBC) is a parallel computation approach with drastically reduced energy consumption. NBC uses biomolecular motors to propel cytoskeletal filaments through nanofabricated networks that encode mathematical problems. By stochastically exploring possible paths through the networks, the cytoskeletal filaments find possible solutions. However, to date, no NBC algorithm for 3\u2010SAT has been available. Herein, an algorithm that converts 3\u2010SAT into an NBC\u2010compatible network format is reported and four small 3\u2010SAT instances (with up to three variables and five clauses) using the actin\u2013myosin biomolecular motor system are experimentally solved. Because practical polynomial conversions to 3\u2010SAT exist for many important NP complete problems, the result opens the door to enable NBC to solve small instances of a wide range of problems.<\/jats:p><\/jats:sec>","DOI":"10.1002\/aisy.202200202","type":"journal-article","created":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T21:34:35Z","timestamp":1664746475000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Solving the 3\u2010Satisfiability Problem Using Network\u2010Based Biocomputation"],"prefix":"10.1002","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8027-1585","authenticated-orcid":false,"given":"Jingyuan","family":"Zhu","sequence":"first","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Division of Solid State Physics Lund University  Box 118 22100 Lund Sweden"}]},{"given":"Aseem","family":"Salhotra","sequence":"additional","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Department of Chemistry and Biomedical Sciences Linnaeus University  39182 Kalmar Sweden"}]},{"given":"Christoph Robert","family":"Meinecke","sequence":"additional","affiliation":[{"name":"Center for Microtechnologies Technische Universit\u00e4t Chemnitz  09126 Chemnitz Germany"}]},{"given":"Pradheebha","family":"Surendiran","sequence":"additional","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Division of Solid State Physics Lund University  Box 118 22100 Lund Sweden"}]},{"given":"Roman","family":"Lyttleton","sequence":"additional","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Division of Solid State Physics Lund University  Box 118 22100 Lund Sweden"}]},{"given":"Danny","family":"Reuter","sequence":"additional","affiliation":[{"name":"Center for Microtechnologies Technische Universit\u00e4t Chemnitz  09126 Chemnitz Germany"},{"name":"Department Nano Device Technologies Fraunhofer Institute for Electronic Nano Systems ENAS  09126 Chemnitz Germany"}]},{"given":"Hillel","family":"Kugler","sequence":"additional","affiliation":[{"name":"Faculty of Engineering Bar-Ilan University  Ramat Gan 5290002 Israel"}]},{"given":"Stefan","family":"Diez","sequence":"additional","affiliation":[{"name":"B CUBE - Center for Molecular Bioengineering and Cluster of Excellence Physics of Life Technische Universit\u00e4t Dresden  01307 Dresden Germany"},{"name":"Max Planck Institute of Molecular Cell Biology and Genetics  01307 Dresden Germany"}]},{"given":"Alf","family":"M\u00e5nsson","sequence":"additional","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Department of Chemistry and Biomedical Sciences Linnaeus University  39182 Kalmar Sweden"}]},{"given":"Heiner","family":"Linke","sequence":"additional","affiliation":[{"name":"NanoLund Lund University  Box 118 22100 Lund Sweden"},{"name":"Division of Solid State Physics Lund University  Box 118 22100 Lund Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2315-9247","authenticated-orcid":false,"given":"Till","family":"Korten","sequence":"additional","affiliation":[{"name":"B CUBE - Center for Molecular Bioengineering and Cluster of Excellence Physics of Life Technische Universit\u00e4t Dresden  01307 Dresden Germany"}]}],"member":"311","published-online":{"date-parts":[[2022,10,2]]},"reference":[{"key":"e_1_2_10_2_1","unstructured":"K. L.McMillan presented atInt. Conf. on Computer Aided Verification Boulder CO July 2003."},{"key":"e_1_2_10_3_1","unstructured":"H.Kautz B.Selman presented atIJCAI Stockholm Sweden July-August 1999."},{"key":"e_1_2_10_4_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009"},{"key":"e_1_2_10_5_1","unstructured":"E.Clarke M.Talupur H.Veith D.Wang presented atInt. Conf. on Theory and Applications of Satisfiability Testing Santa Margherita Ligure Italy2003."},{"key":"e_1_2_10_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.79.051915"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0006-3495(03)74907-8"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aab3326"},{"key":"e_1_2_10_9_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_10_10_1","volume-title":"Handbook of Satisfiability","author":"Biere A.","year":"2009"},{"key":"e_1_2_10_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"e_1_2_10_12_1","unstructured":"T. D.Hansen H.Kaplan O.Zamir U.Zwick inProc. of the 51st Annual ACM SIGACT Symp. on Theory of Computing Association for Computing Machinery Phoenix AZ2019."},{"key":"e_1_2_10_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/35003155"},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1069528"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1510825113"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mee.2006.01.198"},{"key":"e_1_2_10_17_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac175d"},{"key":"e_1_2_10_18_1","unstructured":"L.Hardy arXiv preprint quant-ph\/01010122001."},{"key":"e_1_2_10_19_1","unstructured":"W.Guo J.Wang M.He X.Ren Q.Wang W.Tian presented at2018 IEEE 4th Int. Conf. on Computer and Communications (ICCC) IEEE Piscataway NJ December 2018."},{"key":"e_1_2_10_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.83.17.6272"},{"key":"e_1_2_10_21_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/16\/6\/014"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1021\/la060854i"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.accounts.8b00296"},{"key":"e_1_2_10_24_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.9b00249"},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac39b4"},{"key":"e_1_2_10_26_1","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/647265"},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNB.2015.2412036"},{"key":"e_1_2_10_28_1","unstructured":"A. S.Perumal M.Nayak V.Tok\u00e1rov\u00e1 O.Ka\u0161par D. V.Nicolau presented atInt. Conf. on Bio-inspired Information and Communication Cham Swizerland2019."},{"key":"e_1_2_10_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(90)90287-V"},{"key":"e_1_2_10_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bpj.2013.08.044"},{"key":"e_1_2_10_31_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac2a5d"},{"key":"e_1_2_10_32_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac1809"},{"key":"e_1_2_10_33_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac39b4"},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ac2005"},{"key":"e_1_2_10_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2008.2006165"},{"key":"e_1_2_10_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.nantod.2011.02.001"},{"key":"e_1_2_10_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/nnano.2012.82"},{"key":"e_1_2_10_38_1","doi-asserted-by":"publisher","DOI":"10.1088\/2399-1984\/ac7d81"},{"key":"e_1_2_10_39_1","doi-asserted-by":"publisher","DOI":"10.1152\/jappl.1998.85.6.2140"},{"key":"e_1_2_10_40_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.langmuir.8b01415"},{"key":"e_1_2_10_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0076-6879(91)96035-P"},{"key":"e_1_2_10_42_1","doi-asserted-by":"publisher","DOI":"10.1161\/01.RES.73.4.696"},{"key":"e_1_2_10_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.jbchem.a135365"},{"key":"e_1_2_10_44_1","first-page":"164","volume":"85","author":"Pardee J. D.","year":"1982","journal-title":"Methods Cell Biol."},{"key":"e_1_2_10_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ab.2004.12.012"},{"key":"e_1_2_10_46_1","doi-asserted-by":"publisher","DOI":"10.1152\/ajpcell.1992.262.3.C714"},{"key":"e_1_2_10_47_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0055931"},{"key":"e_1_2_10_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10974-019-09505-1"},{"key":"e_1_2_10_49_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.2019"}],"container-title":["Advanced Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/aisy.202200202","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/aisy.202200202","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/advanced.onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/aisy.202200202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T19:29:22Z","timestamp":1759865362000},"score":1,"resource":{"primary":{"URL":"https:\/\/advanced.onlinelibrary.wiley.com\/doi\/10.1002\/aisy.202200202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,2]]},"references-count":48,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1002\/aisy.202200202"],"URL":"https:\/\/doi.org\/10.1002\/aisy.202200202","archive":["Portico"],"relation":{},"ISSN":["2640-4567","2640-4567"],"issn-type":[{"value":"2640-4567","type":"print"},{"value":"2640-4567","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,2]]},"assertion":[{"value":"2022-07-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"2200202"}}