Research Group on Natural Computing

This chapter is devoted to the study of numerical NP-complete problems in the framework of cellular systems with membranes, also called P systems (Păun, 1998). We present efficient solutions to the Subset-Sum and the Knapsack problems. These solutions are obtained via families of P systems with the capability of generating an exponential amount of working space in polynomial time.
Besides, a simulation tool for P systems, written in Prolog, is described. As an illustrative example, a session in the Prolog simulator implementing one of the presented cellular solutions is included.