Search: onr:"swepub:oai:DiVA.org:lnu-117112" >
Solving the 3-Satis...
Solving the 3-Satisfiability Problem Using Network-Based Biocomputation
-
- Zhu, Jingyuan (author)
- Lund University, Sweden
-
- Salhotra, Aseem (author)
- Linnéuniversitetet,Institutionen för kemi och biomedicin (KOB),Lund University, Sweden,Lund University; Linnaeus University
-
- Meinecke, Christoph Robert (author)
- Tech Univ Chemnitz, Germany
-
show more...
-
- Surendiran, Pradheebha (author)
- Lund University, Sweden
-
- Lyttleton, Roman (author)
- Lund University, Sweden
-
- Reuter, Danny (author)
- Tech Univ Chemnitz, Germany;Fraunhofer Inst Elect Nano Syst ENAS, Germany
-
- Kugler, Hillel (author)
- Bar Ilan Univ, Israel
-
- Diez, Stefan (author)
- Tech Univ Dresden, Germany;Max Planck Inst Mol Cell Biol & Genet, Germany
-
- Månsson, Alf (author)
- Linnéuniversitetet,Institutionen för kemi och biomedicin (KOB),Avancerade material,Lund University, Sweden
-
- Linke, Heiner (author)
- Lund University, Sweden
-
- Korten, Till (author)
- Tech Univ Dresden, Germany
-
show less...
-
(creator_code:org_t)
- 2022-10-02
- 2022
- English.
-
In: Advanced Intelligent Systems. - : John Wiley & Sons. - 2640-4567. ; 4:12
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://lnu.diva-por... (primary) (Raw object)
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Biologi -- Biokemi och molekylärbiologi (hsv//swe)
- NATURAL SCIENCES -- Biological Sciences -- Biochemistry and Molecular Biology (hsv//eng)
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Nanoteknik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Nano-technology (hsv//eng)
- NATURVETENSKAP -- Biologi -- Biofysik (hsv//swe)
- NATURAL SCIENCES -- Biological Sciences -- Biophysics (hsv//eng)
Keyword
- molecular motors
- nanofabrication
- network-based biocomputation
- nondeterministic polynomials
- parallel computation
- satisfiability problems
- Biokemi
- Biochemistry
- Data- och informationsvetenskap
- Computer and Information Sciences Computer Science
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database
- By the author/editor
-
Zhu, Jingyuan
-
Salhotra, Aseem
-
Meinecke, Christ ...
-
Surendiran, Prad ...
-
Lyttleton, Roman
-
Reuter, Danny
-
show more...
-
Kugler, Hillel
-
Diez, Stefan
-
Månsson, Alf
-
Linke, Heiner
-
Korten, Till
-
show less...
- About the subject
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Biological Scien ...
-
and Biochemistry and ...
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Mathematics
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Computer and Inf ...
-
and Computer Science ...
-
- ENGINEERING AND TECHNOLOGY
-
ENGINEERING AND ...
-
and Nano technology
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Biological Scien ...
-
and Biophysics
- Articles in the publication
-
Advanced Intelli ...
- By the university
-
Linnaeus University
-
Royal Institute of Technology