Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fl uids in a three-dimensional microfluidic system to solve a nondeterministic ally polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidi c system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute s olutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computati on and control.