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

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

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Pradheebha Surendiran,

Christoph Meinecke,

Aseem Salhotra,

Georg Heldt,

Jingyuan Zhu,

Alf Månsson,

Stefan Diez,

Danny Reuter,

Hillel Kugler,

Heiner Linke,

Till Korten

Publication year - 2022

Publication title -

acs nanoscience au

Language(s) - English

Resource type - Journals

ISSN - 2694-2496

DOI - 10.1021/acsnanoscienceau.2c00013

Subject(s) - cover (algebra) , computer science , modular design , nondeterministic algorithm , scheduling (production processes) , distributed computing , electricity , np , theoretical computer science , mathematical optimization , algorithm , mathematics , engineering , electrical engineering , mechanical engineering , turing machine , computation , operating system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research