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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)396-403
JournalACS Nanoscience AU
Volume2
Issue number5
Early online date2022
DOIs
Publication statusPublished - 2022

Subject classification (UKÄ)

  • Nano Technology
  • Computer Engineering
  • Condensed Matter Physics

Keywords

  • biocomputation
  • biofunctionalization
  • computational nanotechnology
  • molecular motors
  • nanobiotechnology
  • parallel computing

Fingerprint

Dive into the research topics of 'Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation'. Together they form a unique fingerprint.

Cite this