Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation
The 3‐satisfiability Problem (3‐SAT) 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 n...
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-12-01
|
| Series: | Advanced Intelligent Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1002/aisy.202200202 |
| _version_ | 1797978856128249856 |
|---|---|
| author | Jingyuan Zhu Aseem Salhotra Christoph Robert Meinecke Pradheebha Surendiran Roman Lyttleton Danny Reuter Hillel Kugler Stefan Diez Alf Månsson Heiner Linke Till Korten |
| author_facet | Jingyuan Zhu Aseem Salhotra Christoph Robert Meinecke Pradheebha Surendiran Roman Lyttleton Danny Reuter Hillel Kugler Stefan Diez Alf Månsson Heiner Linke Till Korten |
| author_sort | Jingyuan Zhu |
| collection | DOAJ |
| description | The 3‐satisfiability Problem (3‐SAT) 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‐SAT instances. Thus, large 3‐SAT instances require excessive amounts of energy to solve with serial electronic computers. Network‐based 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‐SAT has been available. Herein, an algorithm that converts 3‐SAT into an NBC‐compatible network format is reported and four small 3‐SAT instances (with up to three variables and five clauses) using the actin–myosin biomolecular motor system are experimentally solved. Because practical polynomial conversions to 3‐SAT 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. |
| first_indexed | 2024-04-11T05:29:38Z |
| format | Article |
| id | doaj.art-b6ef298c7c3a4354be2768b55cfedbea |
| institution | Directory Open Access Journal |
| issn | 2640-4567 |
| language | English |
| last_indexed | 2024-04-11T05:29:38Z |
| publishDate | 2022-12-01 |
| publisher | Wiley |
| record_format | Article |
| series | Advanced Intelligent Systems |
| spelling | doaj.art-b6ef298c7c3a4354be2768b55cfedbea2022-12-23T04:16:31ZengWileyAdvanced Intelligent Systems2640-45672022-12-01412n/an/a10.1002/aisy.202200202Solving the 3‐Satisfiability Problem Using Network‐Based BiocomputationJingyuan Zhu0Aseem Salhotra1Christoph Robert Meinecke2Pradheebha Surendiran3Roman Lyttleton4Danny Reuter5Hillel Kugler6Stefan Diez7Alf Månsson8Heiner Linke9Till Korten10NanoLund Lund University Box 118 22100 Lund SwedenNanoLund Lund University Box 118 22100 Lund SwedenCenter for Microtechnologies Technische Universität Chemnitz 09126 Chemnitz GermanyNanoLund Lund University Box 118 22100 Lund SwedenNanoLund Lund University Box 118 22100 Lund SwedenCenter for Microtechnologies Technische Universität Chemnitz 09126 Chemnitz GermanyFaculty of Engineering Bar-Ilan University Ramat Gan 5290002 IsraelB CUBE - Center for Molecular Bioengineering and Cluster of Excellence Physics of Life Technische Universität Dresden 01307 Dresden GermanyNanoLund Lund University Box 118 22100 Lund SwedenNanoLund Lund University Box 118 22100 Lund SwedenB CUBE - Center for Molecular Bioengineering and Cluster of Excellence Physics of Life Technische Universität Dresden 01307 Dresden GermanyThe 3‐satisfiability Problem (3‐SAT) 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‐SAT instances. Thus, large 3‐SAT instances require excessive amounts of energy to solve with serial electronic computers. Network‐based 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‐SAT has been available. Herein, an algorithm that converts 3‐SAT into an NBC‐compatible network format is reported and four small 3‐SAT instances (with up to three variables and five clauses) using the actin–myosin biomolecular motor system are experimentally solved. Because practical polynomial conversions to 3‐SAT 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.https://doi.org/10.1002/aisy.202200202molecular motorsnanofabricationnetwork-based biocomputationnondeterministic polynomialsparallel computationsatisfiability problems |
| spellingShingle | Jingyuan Zhu Aseem Salhotra Christoph Robert Meinecke Pradheebha Surendiran Roman Lyttleton Danny Reuter Hillel Kugler Stefan Diez Alf Månsson Heiner Linke Till Korten Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation Advanced Intelligent Systems molecular motors nanofabrication network-based biocomputation nondeterministic polynomials parallel computation satisfiability problems |
| title | Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation |
| title_full | Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation |
| title_fullStr | Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation |
| title_full_unstemmed | Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation |
| title_short | Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation |
| title_sort | solving the 3 satisfiability problem using network based biocomputation |
| topic | molecular motors nanofabrication network-based biocomputation nondeterministic polynomials parallel computation satisfiability problems |
| url | https://doi.org/10.1002/aisy.202200202 |
| work_keys_str_mv | AT jingyuanzhu solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT aseemsalhotra solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT christophrobertmeinecke solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT pradheebhasurendiran solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT romanlyttleton solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT dannyreuter solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT hillelkugler solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT stefandiez solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT alfmansson solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT heinerlinke solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation AT tillkorten solvingthe3satisfiabilityproblemusingnetworkbasedbiocomputation |