Computational Complexity of Simple P Systems

Abstract

We introduce a new class of membrane systems called simple P systems, and study its computational complexity using the classical theory. We start by presenting the knapsack problem and analyzing its space and time complexities. Then we study the computational complexity of simple P systems by considering the static allocation of resources enabling the parallel application of the rules. We show that the problem of allocating resources for simple P systems is NP-complete by reducing it to the knapsack problem. Thus we express the computational complexity of this class of P systems in terms of classical complexity theory.