Active P-Colonies

P-Systems are abstract machines inspired to the behaviour of cells which we can see like simple biological processing units. Many types of P-Systems have been developed considering different aspects of the cells working principles, obtaining different computational models. In this paper we introduce Active P-Colonies (APC), a variant of the model P -Colony systems. P-Colony systems are a model of computation based on the collaboration among different agents placed in a shared passive environment (i.e. a space where no computing operations take place). First of all, we show that using the P-Colony system basic model it is not possible to solve problems in the computational class NP (unless P 1/4 NP). Inspired by what has been done for the basic variant of P-Systems, we extend the original model by including new types of rules and new biological behaviours like duplication and membrane dissolution. In fact, in APC the agents are able to duplicate themselves obtaining new processing units having the same computational power as the original unit. The cells can also dissolve their membrane, releasing the contents into the environment. The obtained systems are able to solve in polynomial time (and exponential space) computationally hard problems. In particular, we focus on the development of systems able to solve problems in the classes NP (SAT), coNP (UNSAT) and #P (#SAT). (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

P-Systems are abstract machines inspired by the behavior of cells, which can be seen as simple biological processing units. In this paper, a variant called Active P-Colonies (APC) is introduced, which extends the original model by including new types of rules and biological behaviors. The obtained systems are able to solve computationally hard problems and are focused on solving problems in NP (SAT), coNP (UNSAT), and #P (#SAT) classes.