Deciding networks of evolutionary processors

Florin Manea

Abstract. In this paper we discuss the usage of Accepting Networks of Evolutionary Processors (ANEPs for short) as deciding devices. In this context we define a new halting condition for this model, which seems more coherent with the rest of the theory than the previous such definition, and show that all the computability results reported so far remain valid in the new framework. Moreover, we give a direct and efficient simulation of an arbitrary ANEP by a complete ANEP, thus, showing that the efficiency of deciding a language by ANEPs is not influenced by the network’s topology. Finally, we obtain a surprising characterization of PNP[log] as the class of languages that can be decided in polynomial time by ANEPs.

Comments are closed.