부산대학교 도서관

Membrane computing is a distributed parallel computing paradigm inspired by the way living cells process chemical substances, energy and information. The processor units are abstractions of biological membranes: selectively permeable barriers and their inner compartments. When membranes take an active role in the functioning of the system, that is, when they can be created, dissolved, or divided, we speak of P systems with active membranes. \par Cell division in membrane systems is a mechanism that produces identical copies of complete compartments (together with their contents); therefore active P systems can usually give polynomial time solutions to difficult computational problems: they can make use of cell division rules as a mechanism to produce an exponential workspace in linear time. \par The paper studies a variant called polarizationless P systems with active membranes, where instead of cell division the authors introduce cell separation rules inspired by the membrane fission process by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane are not duplicated, but only distributed between the new membranes. \par The paper introduces separation rules also for non-elementary membranes (these types of rules have not been studied so far), and investigates the computational efficiency of the resulting systems where the so-called object evolution rules also have restricted forms: noncooperating rules (rewriting rules having at most one object on their left-hand sides), primary minimal cooperation rules (rules having at most two objects on their left-hand sides), and bounded minimal cooperation rules (rules having at most two objects on both sides with the additional restriction that the number of objects on the right-hand side cannot be less than the number of objects on the left-hand side). \par The first result shows that dissolution rules play a relevant role in the computational efficiency of systems with noncooperating rules: without dissolution, they can only solve problems from the class {\bf P} in polynomial time. On the other hand, according to the second result, if primary minimal cooperating rules are allowed, then the SAT problem can be solved in polynomial time (even without allowing the separation of non-elementary membranes). Since it was shown in [L. Valencia-Cabrera et al., in {\it Proceedings of the 14th Brainstorming Week on Membrane Computing}, 327--356, E.~T.~S. de Ingeniería Informática, Sevilla, 2016] that systems with bounded minimal cooperation rules characterize only the class {\bf P}, a new frontier of tractability has been obtained: in the framework of polarizationless P systems with active membranes and separation rules, passing from bounded minimal cooperation to primary minimal cooperation amounts to passing from non-efficiency to efficiency (assuming that {\bf P} is not equal to {\bf NP}).