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. (Figure presented.)

Non-deterministic polynomial (NP-) complete problems, whose number of possible solutions grows exponentially with the number of variables, require by necessity massively parallel computation. Because sequential computers, such as solid state-based ones, can solve only small instances of these problems within a reasonable time frame, parallel computation using motile biological agents in nano- and micro-scale networks has been proposed as an alternative computational paradigm. Previous work demonstrated that protein molecular motors-driven cytoskeletal filaments are able to solve a small instance of an NP complete problem, i.e. the subset sum problem, embedded in a network. Autonomously moving bacteria are interesting alternatives to these motor driven filaments for solving such problems, because they are easier to operate with, and have the possible advantage of biological cell division. Before scaling up to large computational networks, bacterial motility behaviour in various geometrical structures has to be characterised, the stochastic traffic splitting in the junctions of computation devices has to be optimized, and the computational error rates have to be minimized. In this work, test structures and junctions have been designed, fabricated, tested, and optimized, leading to specific design rules and fabrication flowcharts, resulting in correctly functioning bio-computation networks.

Particle defects are important contributors to yield loss in semi-conductor manufacturing. Particles need to be detected and characterized in order to determine and eliminate their root cause. We have conceived a process flow for advanced defect classification (ADC) that distinguishes three consecutive steps; detection, review and classification. For defect detection, TNO has developed the Rapid Nano (RN3) particle scanner, which illuminates the sample from nine azimuth angles. The RN3 is capable of detecting 42 nm Latex Sphere Equivalent (LSE) particles on XXX-flat Silicon wafers. For each sample, the lower detection limit (LDL) can be verified by an analysis of the speckle signal, which originates from the surface roughness of the substrate. In detection-mode (RN3.1), the signal from all illumination angles is added. In review-mode (RN3.9), the signals from all nine arms are recorded individually and analyzed in order to retrieve additional information on the shape and size of deep sub-wavelength defects. This paper presents experimental and modelling results on the extraction of shape information from the RN3.9 multi-azimuth signal such as aspect ratio, skewness, and orientation of test defects. Both modeling and experimental work confirm that the RN3.9 signal contains detailed defect shape information. After review by RN3.9, defects are coarsely classified, yielding a purified Defect-of-Interest (DoI) list for further analysis on slower metrology tools, such as SEM, AFM or HIM, that provide more detailed review data and further classification. Purifying the DoI list via optical metrology with RN3.9 will make inspection time on slower review tools more efficient.