Solving Problems Through a Single Membrane System

The tape of a deterministic Turing machine contains an unbounded number of cells. Thanks to that, a single machine can solve decision problems with an infinite number of instances. Nevertheless, in the framework of membrane computing, traditionally a \solution" to an abstract decision problem consists of a family of membrane systems (where each system of the family is associated with a finite set of instances of the problem to be solved). An interesting question is to analyze the possibility to find a single membrane system able to deal with the infinitely many instances of a decision problem. In this context, it is fundamental to define precisely how the instances of the problem are introduced into the system. In this paper, two different methods are considered. The first one relies on a pre-computing process, where a polynomial-time computable function will be in charge of producing a multiset of objects associated with the instance to be solved. On the other hand, the second one assumes that the input alphabet of the system is equal to the alphabet of instances, and therefore instances are directly introduced in the initial configuration of the system. Polynomial complexity classes associated with these two approaches are introduced and some complexity aspects are studied.