Abstract

Abstract The solution space of Non-deterministic Polynomial (NP) complete problems grows exponentially with input size. Consequently, large NP complete problems cannot be solved in an acceptable time by fast, but sequential electronic computers, nor presently by alternative, parallel computing approaches. Here, we report that the bacterial exploration of microfluidic networks that encode instances of the Subset Sum Problem (SSP) is equivalent to solving this NP-complete problem. Significantly, the ability of bacteria to multiply in confined environments translates in the amplification of the computational parallelism, with computing resources growing naturally to match the size of a given combinatorial problem. A scaling analysis of the time needed by bacteria to solve SSP problems encoded in microfluidic networks identifies the point where they are theoretically expected to outperform fast solid-state computers. These results, namely massively parallel, design-driven low error operation, low energy requirement for computing, and exponentially growing computing resources, suggest that bacterial-driven biocomputation on networks holds the potential to scale up successfully.