Significance Electronic computers are extremely powerful at performing a high number of operations at very high speeds, sequentially. However, they struggle with combinatorial tasks that can be solved faster if many operations are performed in parallel. Here, we present proof-of-concept of a parallel computer by solving the specific instance {2, 5, 9} of a classical nondeterministic-polynomial-time complete (“NP-complete”) problem, the subset sum problem. The computer consists of a specifically designed, nanostructured network explored by a large number of molecular-motor-driven, protein filaments. This system is highly energy efficient, thus avoiding the heating issues limiting electronic computers. We discuss the technical advances necessary to solve larger combinatorial problems than existing computation devices, potentially leading to a new way to tackle difficult mathematical problems.

Abstract The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.

Many combinatorial problems of practical importance, such as the design and verification of circuits (1), the folding (2) and design (3) of proteins, and optimal network routing (4), require that a large number of possible candidate solutions are explored in a brute-force manner to discover the actual solution. Because the time required for solving these problems grows exponentially with their size, they are intractable for conventional electronic computers, which operate sequentially, leading to impractical computing times even for medium-sized problems. Solving such problems therefore requires efficient parallel-computation approaches (5). However, the approaches proposed so far suffer from drawbacks that have prevented their implementation. For example, DNA computation, which generates mathematical solutions by recombining DNA strands (6, 7), or DNA static (8) or dynamic (9) nanostructures, is limited by the need for impractically large amounts of DNA (10⇓⇓–13). Quantum computation is limited in scale by decoherence and by the small number of qubits that can be integrated (14). Microfluidics-based parallel computation (15) is difficult to scale up in practice due to rapidly diverging physical size and complexity of the computation devices with the size of the problem, as well as the need for impractically large external pressure.

Here, we propose a parallel-computation approach, which is based on encoding combinatorial problems into the geometry of a physical network of lithographically defined channels, followed by exploration of the network in a parallel fashion using a large number of independent agents, with very high energy efficiency. To demonstrate operational functionality, we applied it to a small instance of a benchmark classical nondeterministic-polynomial-time complete (NP-complete) problem (16), the subset sum problem (SSP) (Fig. 1). This problem asks whether, given a set S = {s 1 , s 2 , ..., s N } of N integers, there exists a subset of S whose elements sum to a target sum, T. More formally, the question is whether there is a solution ∑ i = 1 N w i s i where w i ∈ {0, 1}, for any given T from 0 to ∑ i = 1 N s i . To find all possible subset sums by exploring all possible subsets requires the testing of 2N different combinations, which––even for modest values of N––is impractical on electronic computers because of exponentially increasing time requirements (SI Appendix, section S1). Although more sophisticated algorithms exist (17⇓–19), none of these avoids the exponentially growing exploration time, a property that is harnessed in some cryptography systems to generate encoded messages (20).

Fig. 1. Computation network for the SSP {2, 5, 9}. The agents enter the network from the top-left corner. Filled circles represent split junctions where it is equally probable that agents continue straight ahead or turn. Empty circles represent pass junctions where agents continue straight ahead. Moving diagonally down at a split junction corresponds to adding that integer (numbers 2 and 9 for the yellow example path). The actual value of the integer potentially added at a split junction is determined by the number of rows of junctions until the next split junction. The exit numbers correspond to the target sums T (potential solutions) represented by each exit; correct results for this particular set {2, 5, 9} are labeled in green, and incorrect results (where no agents will arrive) are labeled in magenta. The working principle is also detailed in Movie S1.

Our approach replaces the requirement for exponentially growing time needed by traditional, electronic computers to solve NP-complete problems, with the requirement for an exponentially growing number of independent computing agents. We use a proof-of-concept device to successfully solve the specific three-variable instance {2, 5, 9} of the SSP. Key technical advancements necessary to scale up our approach to be of practical relevance include the need to reduce error rates and to supply sufficiently many computing agents. We identify several possible approaches to address these requirements.

Discussion We developed a parallel-computation approach based on encoding combinatorial problems into the geometry of physical networks. We showed that these networks can be manufactured lithographically and explored using independent agents. Using such a device, we demonstrated the solution of one particular three-variable instance of the SSP. Notably, once the device is loaded with the required number of agents, the effective computational time for NP-complete problems grows only polynomially, e.g., as N2 if the elements of S are approximately equidistantly spaced. This is in contrast to traditional, sequentially operating, electronic computers, where the time required to explore every possible solution sequentially would scale exponentially as 2N. However, it is inherent to combinatorial and NP-complete problems (assuming P! = NP) that the exploration of the entire solution space requires the use of exponentially increasing amounts of some resource, such as time, space, or material. In the present case this fundamental requirement manifests itself in the number of agents needed, which grows exponentially with 2N. Effectively we are trading the need of time for the need of molecular mass. The error rates of this first device are too large for scaling up to problems containing more than ∼10 variables (see SI Appendix, section S1 for a more detailed scaling analysis). Nevertheless, we argue that our approach has the potential to be more scalable in practice than other approaches because it offers several advantages: (i) Myosin II and kinesin-1 molecular motors use a distributed energy supply (ATP in the surrounding solution), thus eliminating the need for external forces (such as pressure or an electric potential) to drive the computation. This need inherently prevents, for example, microfluidic approaches from scaling up, because in these devices the pressures needed to pump fluid through the network become prohibitively large for large N (30). (ii) The molecular motors operate in a highly energy-efficient manner. As a result, the approach demonstrated here consumes orders of magnitude less energy per operation compared with both electronic and microfluidic computers, eliminating issues related to the dissipation of heat. Specifically, we estimate an energy cost of 2–5 × 10−14 J per operation for a molecular-motor-based device compared with about 3–6 × 10−10 J per operation for the most advanced electronic computers, or an estimated minimum of 10−12 J per operation for microfluidics-based computers (SI Appendix, section S7). (iii) The networks in which the problems are encoded in our approach are planar and comprise standardized modules, therefore being fully scalable with existing technology (see SI Appendix, section S1 for a more detailed discussion). Thus, they avoid potential engineering challenges associated with building large-scale 3D microfluidics devices. Most importantly, however, we foresee several practical solutions to managing the need for exponentially increasing numbers of agents that we highlighted above. (i) The number of agents can self-adjust to the problem size. Specifically, cytoskeletal filaments can self-replicate as they traverse the network by enzymatic splitting and simultaneous elongation (31, 32). Alternatively, self-propelled, dividing microorganisms can be used as agents (33⇓–35). Thus, the larger the network, the more the agents will multiply, in an exponential fashion. Any kind of agent multiplication scheme will also solve potential problems with sequential feeding of the agents into the network through a single entrance, which represents a bottleneck for large N. Moreover, for cytoskeletal filaments, the splitting and elongation rates will be limited by the global concentrations of enzymes and filament subunits, respectively. Thus, multiplication will be negatively regulated in parts of the network where the agent density is high (i.e., above the density needed for successful computation), consequently counteracting the risk of channel clogging. (ii) The NP-complete problem is encoded into a planar, physical network and not into the agents themselves. This simplifies fabrication and encoding because the network that encodes the problem grows polynomially, whereas the exponentially scaling number of cytoskeletal filaments can be fabricated in bulk. This is in contrast to DNA computing, where large amounts of DNA need to be specifically synthesized for each problem. Furthermore, because of their generic nature, agents can continue to explore the network as long as ATP is available, which means they can be by recirculated and used more than once (SI Appendix, Fig. S2.1). (iii) Because our device implements basic addition operations, it can benefit from existing optimized algorithms and can be easily combined with a conventional computer to form a hybrid device. For example, an electronic computer could be used to, first, solve a subset of the largest numbers in the SSP. Then, the solutions calculated by the computer would be passed on to a set of biological computers described here, drastically reducing the number of agents needed because the biological computer solves only that part of the problem that overwhelms the electronic computer. Furthermore, the time needed to feed the filaments into the network would be further reduced because many entrances can be used in parallel. An extended analysis of scaling and energy considerations is presented in SI Appendix, sections S1 and S7, respectively. Summarizing, the technical advances that would be necessary for a future device able to challenge an electronic computer are (i) scaling up of the physical network size from currently ∼100 × 100 µm2 to wafer size, which is achievable by current patterning technology. (ii) Reduction of the filament feeding time, which can be achieved by using networks with multiple entrances, or by self-replicating filaments, see above. (iii) Reduction of pass-junction error rates. We expect that this can be realized by simulation-driven design (such as described in SI Appendix, section S4), by evolutionary algorithms for designing the junction geometries (36, 37), or by using 3D geometries such as bridges or tunnels (38) which would offer zero error rates at pass junctions. (iv) To circumvent the inherent difficulties of tracking large numbers of individual filaments, automatic readout schemes at exits of interest can be used (39). (v) Programmable devices which can flexibly encode different problems could be achieved by using heat-controlled (40) or electrostatic (41) gates in only one programmable type of junction instead of the two (isomorphic) static junctions. (vi) Finally, filaments can be prevented from attaching to or detaching from the network by using closed channels with porous openings for allowing the supply of ATP (42). The potential practical relevance of our approach goes beyond solving SSP, because all NP-complete problems can be converted to one another using a polynomial-time conversion (7, 43) and due to the general nature of our SSP computation network (namely a computer that can perform addition, and, by using right-to-left diagonals, also subtraction). Therefore, our approach has the potential to be general and to be developed further to enable the efficient encoding and solving of a wide range of large-scale problems. Accomplishing this would move forward (but not remove) the limit of the size of combinatorial problems that can be solved.

Materials and Methods Summary Please see the SI Appendix for a detailed description of the materials and methods. Fabrication of Computational Networks for Use with the Actin–Myosin System. Electron-beam lithography (EBL) was used for pattern formation in a poly(methyl methacrylate) (PMMA) resist on a SiO 2 -coated Si substrate. After development and O 2 -plasma-ashing [to ensure that the PMMA was hydrophilic and therefore unable to support motility (27)], the sample was silanized with trimethylchlorosilane to promote motility on the floor of the exposed SiO 2 substrate (44). Wetting of the surface was performed to reduce the possibility of air bubbles forming in the channels (45). Fabrication of Computational Networks for Use with the Microtubule–Kinesin System. A silicon wafer was sputter-deposited with Au, sandwiched between two Ti adhesion layers. Next, a quartz layer was deposited, followed by a TiW layer and a ZEP520 positive-tone electron-beam resist layer. After exposure in an EBL system and development, the TiW, the quartz, and the upper Ti layers were etched by reactive ion etching down to the Au layer. Finally, the resist residue and the TiW were removed. Actin–Myosin in Vitro Motility Assays. The in vitro motility assays were performed at 26–29 °C, as described previously (46). Briefly, the flow cell was preincubated with (i) heavy meromyosin (47) (120 µg mL−1) for 4 min; (ii) 1 mg mL−1 bovine serum albumin for 1 min; (iii) rhodamine-phalloidin–labeled actin (48) filaments (10-nM monomeric concentration) for 1 min. The flow cell was washed both before and after actin filament incubation. Next, the flow cell was incubated with rigor solution (without ATP) for initial observations. Motility was initiated by introducing a MgAdenosine-5′-triphosphate (MgATP)-containing assay solution. Microtubule–Kinesin in Vitro Motility Assays. Microtubule–kinesin gliding assays were performed using full-length kinesin-1 (kinesin) from Drosophila (49) and rhodamine-labeled tubulin (50) by following a procedure (51) that was upgraded for motility in nanochannels (52). The SiO 2 surface of the computational chip was passivated with 2-[Methoxy(poly-ethyleneoxy) propyl] trimethoxysilane] to prevent protein binding anywhere except on the gold bottom of the channels. Flow cells were perfused with (i) casein-containing solution (0.5 mg ml−1, 5 min); (ii) kinesin solution (2 nM, 5 min); and (iii) motility solution containing 1 mM ATP and rhodamine-labeled, taxol-stabilized. Imaging Methods. Rhodamine-labeled cytoskeletal filaments were observed using inverted fluorescence microscopes. Images were recorded with electron-multiplying charge-coupled device cameras and analyzed with ImageJ (imagej.nih.gov/ij/). Microtubule paths were tracked with software developed in-house (53).

Acknowledgments Dan V. Nicolau Jr. thanks Grant Shoffner and Yue Shark Yu from University of California, Berkeley, for help in running stochastic simulations. Financially supported by the European Union Seventh Framework Programme (FP7/2007-2011) under Grant Agreements 228971 [Molecular Nano Devices (MONAD)] and 613044 [Parallel computing based on designed networks explored by self-propelled, biological agents (ABACUS)]; Defense Advanced Research Projects Agency under Grant Agreement N66001-03-1-8913; by NanoLund; by the Miller Foundation; by the Swedish Research Council (Projects 621-2010-5146 and 2010-4527); The Carl Trygger Foundation, German Research Foundation within the Cluster of Excellence Center for Advancing Electronics Dresden and the Heisenberg Program; and by Linnaeus University.

Footnotes Author contributions: Dan V. Nicolau Jr. and Dan V. Nicolau conceived the calculation method and designed the overall network; F.C.M.J.M.v.D designed the junctions; M.L., T.K., F.C.M.J.M.v.D, A.M., S.D., and H.L., designed the device layouts; M.L. and F.C.M.J.M.v.D fabricated the devices; M.L., T.K., M.P., and E.B. ran motility experiments and analyzed motility data; Dan V. Nicolau Jr., T.K., and A.M. carried out numerical simulations; Dan V. Nicolau initiated the project; Dan V. Nicolau and H.L. coordinated the project; and Dan V. Nicolau Jr., M.L., T.K., F.C.M.J.M.v.D., M.P., E.B., A.M., S.D., H.L., and Dan V. Nicolau contributed to planning the work, to data interpretation, and to writing the manuscript.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission. H.K. is a guest editor invited by the Editorial Board.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1510825113/-/DCSupplemental.