Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

Pradheebha Surendiran; Christoph Robert Meinecke; Aseem Salhotra; Georg Heldt; Jingyuan Zhu; Alf Månsson; Stefan Diez; Danny Reuter; Hillel Kugler; Heiner Linke; Till Korten

doi:10.1021/acsnanoscienceau.2c00013

Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

Pradheebha Surendiran, Christoph Robert Meinecke, Aseem Salhotra, Georg Heldt, Jingyuan Zhu, Alf Månsson, Stefan Diez, Danny Reuter, Hillel Kugler, Heiner Linke, Till Korten

Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift › Peer review

Sammanfattning

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.

Originalspråk	engelska
Sidor (från-till)	396-403
Tidskrift	ACS Nanoscience AU
Volym	2
Nummer	5
Tidigt onlinedatum	2022
DOI	https://doi.org/10.1021/acsnanoscienceau.2c00013
Status	Published - 2022

Ämnesklassifikation (UKÄ)

Nanoteknik
Datorteknik
Den kondenserade materiens fysik

Tillgång till dokument

10.1021/acsnanoscienceau.2c00013Licens: CC BY

Citera det här

@article{bbbe8e784a084c97a734be76dab19840,

title = "Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation",

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 greater in comparison to the current state of the art for NBC.",

keywords = "biocomputation, biofunctionalization, computational nanotechnology, molecular motors, nanobiotechnology, parallel computing",

author = "Pradheebha Surendiran and Meinecke, {Christoph Robert} and Aseem Salhotra and Georg Heldt and Jingyuan Zhu and Alf M{\aa}nsson and Stefan Diez and Danny Reuter and Hillel Kugler and Heiner Linke and Till Korten",

year = "2022",

doi = "10.1021/acsnanoscienceau.2c00013",

language = "English",

volume = "2",

pages = "396--403",

journal = "ACS Nanoscience AU",

issn = "2694-2496",

publisher = "The American Chemical Society (ACS)",

number = "5 ",

}

TY - JOUR

T1 - Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

AU - Surendiran, Pradheebha

AU - Meinecke, Christoph Robert

AU - Salhotra, Aseem

AU - Heldt, Georg

AU - Zhu, Jingyuan

AU - Månsson, Alf

AU - Diez, Stefan

AU - Reuter, Danny

AU - Kugler, Hillel

AU - Linke, Heiner

AU - Korten, Till

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - biocomputation

KW - biofunctionalization

KW - computational nanotechnology

KW - molecular motors

KW - nanobiotechnology

KW - parallel computing

U2 - 10.1021/acsnanoscienceau.2c00013

DO - 10.1021/acsnanoscienceau.2c00013

M3 - Article

C2 - 36281252

AN - SCOPUS:85136696094

VL - 2

SP - 396

EP - 403

JO - ACS Nanoscience AU

JF - ACS Nanoscience AU

SN - 2694-2496

IS - 5

ER -

Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

Sammanfattning

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Citera det här