On the Communication Complexity of the Vertex Cover Problem and 3-Satisfiability Problem in ECP Systems

摘要

In this paper, the communication complexity of non-confluent solutions for Vertex Cover Problem (VCP) and 3-Satisfiability Problem (3SP) in Evolution-Communication P systems (ECP) are analyzed. We use dynamical communication measures suggested by previous literature in our analysis. Solutions are constructed in several modes of operation: when communication is prioritized over evolution (CPE), when evolution is prioritized over communication (EPC) and when no priority is imposed (CME). VCP and 3SP are problems that have already been problems of interest for works that investigate communication complexity in an ECP system variant called Evolution-Communication P system with Energy (ECPe system). In this paper, we are interested in employing the technique used in ECPe system, this time for solutions in ECP system.