Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation. (2nd October 2022)

• Record Type: Journal Article
• Authors: Zhu, Jingyuan; Salhotra, Aseem; Meinecke, Christoph Robert; Surendiran, Pradheebha; Lyttleton, Roman; Reuter, Danny; Kugler, Hillel; Diez, Stefan; Månsson, Alf; Linke, Heiner; Korten, Till
• Is Part Of: Advanced intelligent systems. Volume 4:Number 12(2022)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2022-10-02
• Subjects: molecular motors -- nanofabrication -- network-based biocomputation -- nondeterministic polynomials -- parallel computation -- satisfiability problems; Artificial intelligence -- Periodicals; Robotics -- Periodicals; Control theory -- Periodicals; 006.3
• DOI: 10.1002/aisy.202200202
• Languages: English
• ISSNs: 2640-4567

Abstract

Abstract : 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. Abstract : Herein, an algorithm that encodes the 3‐satisfiability problem (3‐SAT) into network format is presented. Four small 3‐SAT instances with up to three variables and five clauses are solved experimentally; using myosin‐propelled actin filaments exploring nanofabricated 3‐SAT networks in a highly energy‐efficient manner.