Research Group on Natural Computing

We examine the computing power and complexity of P systems
which use two strategies of applying the rules. One strategy is to maximize the
number of objects used in rules and the other is to maximize the number of rules
applied in each membrane. For P systems with cooperative multiset rewriting
rules, P systems with active membranes, and P systems with symport/antiport
rules we prove the computational universality for both these types of parallelism.
The computational complexity of the maximum consuming systems is studied for
systems with cooperative rules of two types, by using two known combinatorial
NP-complete problems, namely the knapsack problem and the integer linear
programming.