Practically Error-Free Junctions Enable Solving Large Instances of Exact Cover Problems Using Network-Based Biocomputation

Abstract

Network-based biocomputing (NBC) presents an energy-efficient, parallel computing approach for solving nondeterministic polynomial time (NP) complete problems by leveraging motor-driven cytoskeletal filaments that explore all possible solutions through nanofabricated networks in a massively parallel fashion. However, guiding errors at pass junctions, where filaments deviate from their intended path, currently limit the scalability of NBC systems. In this study, we addressed this critical challenge by fabricating sub-200 nm channel geometries using modified electron-beam-lithography and reactive-ion-etching protocols to physically constrain the trajectories of kinesin-driven microtubules and enhance path fidelity. Investigating junction designs with varying channel widths, we demonstrate that reducing channel width significantly lowers junction error rates. Practically error-free junction performance was achieved by scaling down the entire network geometry by a factor of two. These optimized junctions were incorporated into NBC networks that successfully solved 24- and 25-set instances of the Exact Cover problem, representing solution spaces of approximately 16 million and 33 million, respectively. This work establishes a new benchmark in NBC performance and represents a computational scale far beyond what has been achieved in prior demonstrations.