Networks of Evolutionary Processors: Results and Perspectives

Abstract

The goal of this chapter is to survey, in a systematic and uniform way, the main results regarding different computational aspects of hybrid networks of evolutionary processors viewed both as generating and accepting devices, as well as solving problems with these mechanisms. We first show that generating hybrid networks of evolutionary processors are computationally complete. The same computational power is reached by accepting hybrid networks of evolutionary processors. Then, we define a computational complexity class of accepting these networks and prove that this class equals the traditional class NP. In another section, we present a few NP-complete problems and recall how they can be solved in linear time by accepting networks of evolutionary processors with linearly bounded resources (nodes, rules, symbols). Finally, we discuss some possible directions for further research.