Amplification of computational power by the multiplication of bacteria exploring microfluidic networks encoding...

Computational resources required for solving NP-complete problems grow exponentially with a polynomial increase in problem size. This exponentially increasing computational resource is runtime for sequential electronic computers and space for massively parallel DNA computing. Here, we report the proof of concept of a computer, whose operation consists in the exploration by motile bacteria of a microfluidic network encoding an algorithm for solving the Subset Sum Problem (SSP)-a classic NP-complete problem. Significantly, this computer performs operations combinatorially, via natural multiplication of bacteria operating as biological CPUs, translating into the continuous amplification of computational power, which grows seamlessly to match the problem size. A scaling analysis identifies the point where biocomputing with multiplying bacteria is expected to outperform electronic computers. The combinatorial, design-driven low error operation, low energy requirement for computing, and exponentially growing computational resources suggest that bacterial-driven biocomputation using microfluidic networks holds the potential to scale up successfully.