Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation
(2022) In ACS Nanoscience AU 2(5). p.396-403- Abstract
Information processing by traditional, serial electronic processors consumes an ever-increasing part of the global electricity supply. An alternative, highly energy efficient, parallel computing paradigm is network-based biocomputation (NBC). In NBC a given combinatorial problem is encoded into a nanofabricated, modular network. Parallel exploration of the network by a very large number of independent molecular-motor-propelled protein filaments solves the encoded problem. Here we demonstrate a significant scale-up of this technology by solving four instances of Exact Cover, a nondeterministic polynomial time (NP) complete problem with applications in resource scheduling. The difficulty of the largest instances solved here is 128 times... (More)
Information processing by traditional, serial electronic processors consumes an ever-increasing part of the global electricity supply. An alternative, highly energy efficient, parallel computing paradigm is network-based biocomputation (NBC). In NBC a given combinatorial problem is encoded into a nanofabricated, modular network. Parallel exploration of the network by a very large number of independent molecular-motor-propelled protein filaments solves the encoded problem. Here we demonstrate a significant scale-up of this technology by solving four instances of Exact Cover, a nondeterministic polynomial time (NP) complete problem with applications in resource scheduling. The difficulty of the largest instances solved here is 128 times greater in comparison to the current state of the art for NBC.
(Less)
- author
- organization
- publishing date
- 2022
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- biocomputation, biofunctionalization, computational nanotechnology, molecular motors, nanobiotechnology, parallel computing
- in
- ACS Nanoscience AU
- volume
- 2
- issue
- 5
- pages
- 396 - 403
- publisher
- The American Chemical Society (ACS)
- external identifiers
-
- pmid:36281252
- scopus:85136696094
- ISSN
- 2694-2496
- DOI
- 10.1021/acsnanoscienceau.2c00013
- language
- English
- LU publication?
- yes
- id
- bbbe8e78-4a08-4c97-a734-be76dab19840
- date added to LUP
- 2022-10-20 13:45:53
- date last changed
- 2024-09-20 05:26:24
@article{bbbe8e78-4a08-4c97-a734-be76dab19840, abstract = {{<p>Information processing by traditional, serial electronic processors consumes an ever-increasing part of the global electricity supply. An alternative, highly energy efficient, parallel computing paradigm is network-based biocomputation (NBC). In NBC a given combinatorial problem is encoded into a nanofabricated, modular network. Parallel exploration of the network by a very large number of independent molecular-motor-propelled protein filaments solves the encoded problem. Here we demonstrate a significant scale-up of this technology by solving four instances of Exact Cover, a nondeterministic polynomial time (NP) complete problem with applications in resource scheduling. The difficulty of the largest instances solved here is 128 times greater in comparison to the current state of the art for NBC.</p>}}, author = {{Surendiran, Pradheebha and Meinecke, Christoph Robert and Salhotra, Aseem and Heldt, Georg and Zhu, Jingyuan and Månsson, Alf and Diez, Stefan and Reuter, Danny and Kugler, Hillel and Linke, Heiner and Korten, Till}}, issn = {{2694-2496}}, keywords = {{biocomputation; biofunctionalization; computational nanotechnology; molecular motors; nanobiotechnology; parallel computing}}, language = {{eng}}, number = {{5}}, pages = {{396--403}}, publisher = {{The American Chemical Society (ACS)}}, series = {{ACS Nanoscience AU}}, title = {{Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation}}, url = {{http://dx.doi.org/10.1021/acsnanoscienceau.2c00013}}, doi = {{10.1021/acsnanoscienceau.2c00013}}, volume = {{2}}, year = {{2022}}, }