P Systems with Evolutional Communication and Division Rules

A widely studied field in the framework of membrane computing is computational complexity theory. While some types of P systems are only capable of efficiently solving problems from the class P, adding one or more syntactic or semantic ingredients to these membrane systems can give them the ability to efficiently solve presumably intractable problems. These ingredients are called to form a frontier of efficiency, in the sense that passing from the first type of P systems to the second type leads to passing from non-efficiency to the presumed efficiency. In this work, a solution to the SAT problem, a well-known NP-complete problem, is obtained by means of a family of recognizer P systems with evolutional symport/antiport rules of length at most (2,1) and division rules where the environment plays a passive role; that is, P systems from (CDEC) over cap (2,1). This result is comparable to the one obtained in the tissue-like counterpart, and gives a glance of a parallelism and the non-evolutionary membrane systems with symport/antiport rules.

Automated summary

A widely studied field in membrane computing is computational complexity theory, where adding syntactic or semantic ingredients to membrane systems can improve their problem-solving efficiency. This study successfully solved the SAT problem using evolutional symport/antiport rules and passive environmental participation in recognizer P systems.