Computing with Autonomous Agents on Graphs
Dan V. Nicolau, Jr
In ongoing work combining theory, simulation and biological experiments, we experimentally demonstrated how self-propelled molecular “agents” moving stochastically through a specially designed nanofabricated network can solve an NP-complete problem (SUBSET SUM) in a massively parallel fashion and, theoretically, in polynomial time. Here, we formally introduce a new computing model, of the distributed parallel type, based on this principle. The computing device, which we call an “N-system”, consists of (a) an appropriately designed digraph encoding a specific instance of a decision problem and (b) a population of agents that evolve on the digraph by jumping between connected nodes at each step of the computation, starting at one or more “input nodes”. The computation terminates when the occupancy status for all nodes is stable, or after some maximum time has elapsed, at which point the result of the computation is completely described by the occupancy status of one or more “output nodes”. The evolution takes place in parallel for all agents that are able to evolve at each step. We show, with an example, how such a system can enumerate the natural numbers as well as how to solve SUBSET SUM in general with this approach. We consider the computational power of this system, describing the power and limitations of N-systems without “stickers” (i.e. without information about agents paths) as well as briefly considering the additional power conferred by stickers. Finally, some issues connected with the physical implementation of N-systems are discussed, as well as their similarities with neural networks, some open problems and future research directions.
Keywords: Networks-based biocomputation, NP-complete problems, unconventional computing