Computational Complexity of Simple P Systems

Issue title: Membrane Computing

Article type: Research Article

Authors: Ciobanu, Gabriel | Resios, Andreas

Affiliations: Romanian Academy, Institute of Computer Science "A.I.Cuza" University of Iaşi Blvd. Carol I no.11, 700506 Iaşi, Romania. gabriel@iit.tuiasi.ro

Note: [] Address for correspondence: "147;A.I.Cuza" University of Iaşi, Blvd. Carol I no.11, 700506 Iaşi, Romania

Abstract: This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.

Keywords: membrane systems, knapsack problem, computational complexity

Journal: Fundamenta Informaticae, vol. 87, no. 1, pp. 49-59, 2008