Journal of Membrane Computing

DP is the class of problems that are the differences between two languages from NP. Most difficult problems from DP are called DP-complete problems, that can be seen as the conjunction of an NP-complete problem and a co-NP-complete problem. It is easy to see that the problem P vs NP is equivalent to the problem P vs DP, and therefore DP-complete problems would be better candidates to attack the conjecture, since they seem to be harder than NP-complete problems. In this paper, a methodology to transform an efficient solution of an NP-complete problem into an efficient solution of a DP-complete problem is applied. More precisely, a solution to is given by means of a uniform family of recognizer polarizationless P systems with active membranes with dissolution rules and division rules for both elementary and non-elementary membranes, and later it is transformed into a solution to the problem -.

P colonies are very simple membrane systems originally derived from the P systems. The 2D P colonies, as a version of P colonies with a two-dimensional environment, were introduced as a theoretical model of the multi-agent system for observing the behavior of a community of very simple agents living in a shared environment. Each agent is equipped with a set of programs consisting of a small number of simple rules. These programs allow the agent to act and move in the environment. Although, the 2D P colonies proved to be suitable for the simulations of various (not only) multi-agent systems, and natural phenomena, like the flash floods, there are phenomena which they are not able to simulate without some additional features or characteristics. One of the ways the agents can share the information is to use the stigmergy, which means to leave some special symbols in the environment. In this paper, we follow our previous research on the 2D P colony. We present a model of the 2D P colony with evolving environment, which allows us to simulate phenomena like the stigmergy, hence to simulate an ant colony.

Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining even computational completeness with only one catalyst. Last year we could show that the derivation mode $$max_{objects}$$ m a x objects , where we only take those multisets of rules which affect the maximal number of objects in the underlying configuration one catalyst is sufficient for obtaining computational completeness without any other ingredients. In this paper we follow this way of research and show that one catalyst is also sufficient for obtaining computational completeness when using specific variants of derivation modes based on non-extendable multisets of rules: we only take those non-extendable multisets whose application yields the maximal number of generated objects or else those non-extendable multisets whose application yields the maximal difference in the number of objects between the newly generated configuration and the current configuration. A similar computational completeness result can even be obtained when omitting the condition of non-extendability of the applied multisets when taking the maximal difference of objects or the maximal number of generated objects. Moreover, we reconsider simple P system with energy control—both symbol and rule energy-controlled P systems equipped with these new variants of derivation modes yield computational completeness.