Search

In the framework of Membrane Computing, several tools to tackle the P versus NP problems by means of frontiers of the efficiency expressed in terms of syntactic or semantic ingredients, have been developed. In this paper, an overview of the results in computational complexity theory concerning to membrane systems (tissue-like and cell-like approach) with symport/antiport rules (where objects are transported without evolving), is given. The frontiers are formulated regarding the length of communication rules, the kind of rules implementing the production of an exponential number of cells/membranes in polynomial time, and the role of the environment. An interesting remark of the obtained results refers that the underlying structure to membrane systems (directed graph versus rooted tree) does not matter in this context. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented which discusses articles on topics including the potential of spiking neural P systems to simulate the behaviour of deterministic finite automata and state transducers, the computational complexity of P systems, and the efficiency of combining the dynamic membrane structure of P systems with the particle swarm optimization.