P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P

P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agust´ın Riscos-N´u˜nez, and Francisco J. Romero-Campero Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {magutier, marper, ariscosn, fran}@us.es Abstract. We study the computational efficiency of recognizer P systems with active membranes without polarizations and without dissolution. The main result of the paper is the following: the polynomial computational complexity class associated with the class of recognizer P systems is equal to the standard complexity class P. 1 Introduction The theory of computation deals with the mechanical solvability of problems, that is, searching solutions that can be described by a finite sequence of elementary processes or instructions. The first goal of this theory is general problem solving; that is, develop principles and methods that are able to solve any problem from a certain class of questions. Acomputational model tries to capture those aspects of mechanical solutions of problems that are relevant to these solutions, including their inherent limitations. In some sense, we can think that computational models design machines according to certain necessity. If we have a mechanically solvable problem and we have a specific algorithm solving it that can be implemented in a real machine, then it is very important to know how much computational resources (time or memory) are required for a given instance, in order to recognize the limitations of the real device. Thus, one of the main goals of the theory of computational complexity is the study of the efficiency of algorithms and their data structures through the analysis of the resources required for solving problems (that is, according to their intrinsic computational difficulty). This theory provides a classification of the abstract problems that allows us to detect their inherent complexity from the computational solutions point of view. Many interesting problems of the real world are presumably intractable and hence it is not possible to execute algorithmic solutions in an electronic computer when we deal with instances of those problems whose size is large. The theoretical limitations of the Turing machines in terms of computational power are also practical limitations to the digital computers. Natural Computing is a new computing area inspired by nature, using concepts, principles and mechanisms underlying natural systems. Evolutionary Computation uses computational models of evolutionary processes as key elements in the design and implementation of computer–based problem solving systems [18]. Neural Networks are inspired in the structures of the brain and nervous system. DNA Computing is based on the computational potential of DNA molecules and on the capacity to handle them. Membrane Computing is inspired by the structure and functioning of living cells, and it is a cross-disciplinary field with contributions by computer scientists, biologists, formal linguists and complexity theoreticians, enriching each others with results, open problems and promising new research lines. This emergent branch of Natural Computing was introduced by Gh. P˘aun in [8]. Since then it has received important attention from the scientific community. In fact, Membrane Computing has been selected by the Institute for Scientific Information, USA, as a fast Emerging Research Front in Computer Science, and [6] was mentioned in [19] as a highly cited paper in October 2003. This new non-deterministic model of computation starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. The devices of this model are called Psystems. Roughly speaking, a P system consists of a cell-like membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous non-deterministic maximally parallel manner1. Inspired in living cells, P systems abstract the way of obtaining new membranes. These processes are basically two: mitosis (membrane division) and autopoiesis (membrane creation). Both ways of generating new membranes have given rise to different variants of P systems: P systems with active membranes, where the new workspace is generated by membrane division, and Psystems with membrane creation, where the new membranes are created from objects. Both models are universal from a computational point of view, but technically, they are pretty different. In fact, nowadays there does not exist any theoretical result which proves that these models can simulate each other in polynomial time. P systems with active membranes have been successfully used to design solutions to well-known NP-complete problems, as SAT [16], Subset Sum [13], Knapsack [14], Bin Packing [15] and Partition [3], but as Gh. P˘aun pointed in [10] “membrane division was much more carefully investigated than membrane creation as a way to obtain tractable solutions to hard problems”. Recently, the first results related to the power and design of algorithms to solve NP problems in these model have arisen (see [4,5]). P systems with active membranes were introduced in [7] with the membranes having polarizations, one of the “electrical charges” 0,−,+, and several times the problem was formulated whether or not these polarizations are necessary in 1A layman-oriented introduction can be found in [9] and further bibliography at [20]. order to obtain polynomial solutions to NP–complete problems. The last current result is that from [1], where one proves that two polarizations suffice. The present paper is both a contribution to this problem, and a contribution to another interesting problem in membrane computing, namely, of characterizing classic complexity classes, such as Pand NP, by means of membrane computing complexity classes. Specifically, we prove that Pis equal to the family of problems which can be solved in a polynomial time by P systems with membrane division, without polarizations and without dissolution. At this moment, we do not know whether this last condition can be avoided, but either result would be of a great interest: if our result would remain true also when using membrane dissolution, then we would have the possitive answer to the problem of removing polarization; the other possibility would indicate a surprising role of the –apparently “innocent”– operation of membrane dissolution, as it will make the difference between efficiency and non–efficiency for P systems with membrane division and without polarization. 2 Preliminaries 2.1 The Reachability Problem The Reachability Problem is the following: given a (directed or undirected) graph, G,andtwonodesa, b, determine whether or not the node bis reachable from a, that is, whether or not there exists a path in the graph from ato b. This problem belongs to the complexity class P. Indeed, it is very easy to design an algorithm running in polynomial time solving it. For example, given a (directed or undirected) graph, G,andtwonodesa, b, we consider a depth– first–search with source a,andwecheckifbis in the tree of the computation forest whose root is a. The total running time of this algorithm is O(|V|+|E|), that is, in the worst case is quadratic in the number of nodes. Morover, this algorithm needs to store a linear number of items (it can be proved that there exists another polynomial time algorithm which uses O(log2(|V|)) space). 2.2 Recognizer P Systems In the structure and functioning of a cell, biological membranes play an essential role. The cell is separated from its environment by means of a skin membrane, and it is internally compartmentalized by means of internal membranes. The main syntatic ingredients of a cell–like membrane system (P system) are the membrane structure,themultisets,andtheevolution rules. –Amembrane structure consists of several membranes arranged hierarchically inside a main membrane (the skin), and delimiting regions (the space in– between a membrane and the immediately inner membranes, if any). Each membrane identifies a region inside the system. A membrane structure can be considered as a rooted tree. –Regions defined by a membrane structure contain objects corresponding to chemical substances present in the compartments of a cell. The objects can be described by symbols or by strings of symbols, in such a way that multiset of objects are placed in the regions of the membrane structure. –The objects can evolve according to given evolution rules, associated with the regions (hence, with the membranes). The semantics of the cell–like membrane systems is defined through a non– deterministic and synchronous model (a global clock is assumed) as follows: –Aconfiguration of a cell–like membrane system consists of a membrane structure and a family of multisets of objects associated with each region of the structure. At the beginning, there is a configuration called the initial configuration of the system. –In each time unit we can transform a given configuration in another configuration by applying the evolution rules to the objects placed inside the regions of the configurations, in a non–deterministic, and maximally parallel manner (the rules are chosen in a non–deterministic way, and in each region all objects that can evolve must do it). In this way, we get transitions from one configuration of the system to the next one. –Acomputation of the system is a (finite or infinite) sequence of configurations such that each configuration –except the initial one– is obtained from the previous one by a transition. –A computation which reaches a configuration where no more rules can be applied to the existing objects, is called a halting computation. –The result of a halting computation is usually defined through the multiset associated with a specific output membrane (or the environment) in the final configuration. That is, a computation in a P system is structured as follows: it starts with the initial configuration of the system, then the computation proceeds, and when it stops the result is to be found in the output membrane. In this paper we use membrane computing as a framework to attack the resolution of decision problems. In order to solve this kind of problems and having in mind the relationship between the solvability of a problem and the recognition of the language associated with it, we consider P systems as recognizer language devices. Definition 1. AP system with input is a tuple (Π, Σ, iΠ),where:(a)Πis a P system, with working alphabet Γ,withpmembranes labelled by 1,...,p,and initial multisets M1,...,Mpassociated with them; (b) Σis an (input) alphabet strictly contained in Γand the initial multisets are over Γ−Σ;(c)iΠis the label of a distinguished (input) membrane. The computations of a P system with input in the form of a multiset over Σ are defined in a natural way, but the initial configuration of (Π, Σ, iΠ)mustbe the initial configuration of the system Πto which we add the input multiset. Definition 2. Let (Π, Σ, iΠ)be a P system with input. Let Γbe the working alphabet of Π,µthe membrane structure, and M1,...,Mpthe initial multisets of Π.Letmbe a multiset over Σ.Theinitial configuration of (Π, Σ, iΠ)with input mis (µ, M1,...,MiΠ∪m,...,Mp). Let (Π, Σ, iΠ) be a P system with input. Let Γbe the working alphabet of Π,µthe membrane structure and M1,...,Mpthe initial multisets of Π.Letm be a multiset over Σ.ThenwedenoteM∗ j={(a, j): a∈M j},for1≤j≤p, and m∗={(a, iΠ): a∈m}. Let us recall that a decision problem Xis a pair (IX,θ X)whereIXis a language over a finite alphabet (whose elements are called instances)andθXis a predicate (a total boolean function) over IX. Definition 3. Let X=(IX,θ X)be a decision problem. Let Π=(Π(n))n∈N be a family of recognizer P systems with input. A polynomial encoding from X to Πis a pair (cod, s)of polynomial time computable functions over IXsuch that for each instance w∈IX,s(w)is a natural number and cod(w)is an input multiset for the system Π(s(w)). It is easy to prove that polynomial encodings are stable under polynomial time reductions. Proposition 1. Let X1,X 2be decision problems. Let rbe a polynomial time reduction from X1to X2.Let(cod, s)be a polynomial encoding from X2to Π. Then (cod ◦r, s ◦r)is a polynomial encoding from X1to Π. Definition 4. Arecognizer P system is a P system with input and external output such that: 1. The working alphabet contains two distinguished elements yes and no. 2. All computations halt. 3. If Cis a computation of the system, then either object yes or object no (but not both) must have been released into the environment, and only in the last step of the computation. In recognizer P systems, we say that a computation Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated with the corresponding halting configuration of C. Hence, these devices send to the environment an accepting or rejecting answer, in the end of their computations. 2.3 A Polynomial Complexity Class in Recognizer P Systems Definition 5. Let X=(IX,θ X)be a decision problem. Let Π=(Π(n))n∈Nbe a family of recognizer P systems with input.Let(cod, s)be a polynomial encoding from Xto Π. –We say that the family Πis sound with regard to (X, cod, s)if the following is true: for each instance of the problem w∈IX, if there exists an accepting computation of Π(s(w)) with input cod(w),thenθX(w)=1. –We say that the family Πis complete with regard to (X, cod, s)if the following is true: for each instance of the problem u∈IX,ifθX(u)=1then every computation of Π(s(u)) with input cod(u)is an accepting computation. Next, we propose to solve a decision problem through a family of P systems constructed in polynomial time by a Turing machine, and verifying that each element of the family processes, in a specified sense, all the instances of equivalent size. We say that these solutions are uniform solutions. Definition 6. Let Rbe a class of recognizer P systems with input membrane. A decision problem X=(IX,θ X)is solvable in polynomial time by a family Π=(Π(n))n∈N, of P systems from R, and we denote this by X∈PMCR,if the following is true: –The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(w)from the instance w∈IX. –There exists a polynomial encoding (cod, s)from IXto Πsuch that •The family Πis polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u)is halting and, moreover, it performs at most p(|u|)steps. •The family Πis sound and complete with regard to (X, cod, s). It is easy to see that the class PMCRis closed under polynomial–time reduction and complement (see [11] for details). 3 Recognizer P Systems with Active Membranes Without Polarizations and Without Dissolution A particularly interesting class of cell–like membrane systems are the systems with active membranes, where the membrane division can be used in order to solve computationally hard problems, e.g., NP-complete problems, in polynomial or even linear time, by a space–time trade-off. In this paper we work with a variant of P systems with active membranes that does not use electrical charges or dissolution rules. Definition 7. A recognizer P system with active membranes without polarizations and without dissolution is a recognizer P system (Π, Γ, iΠ),wheretherules of the associated P system are of the following forms: (a) [a→u]hfor h∈H,a∈Γ,u∈Γ∗: This is an object evolution rule, associated with a membrane labelled with h:anobjecta∈Γbelonging to that membrane evolves to a string u∈Γ∗. (b) a[] h→[b]hfor h∈H,a, b ∈Γ: An object from the region immediately outside a membrane labelled with his introduced in this membrane, possibly transformed into another object. (c) [a]h→b[] hfor h∈H,a, b ∈Γ: An object is sent out from membrane labelled with hto the region immediately outside, possibly transformed into another object. (d) [a]h→[b]h[c]hfor h∈H,a, b, c ∈Γ: An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects. These rules are applied according to the following principles: –All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non– deterministic way), but any object which can evolve by one rule of any form, must evolve. –If at the same time a membrane labelled by his divided by a rule of type (d) and there are objects in this membrane which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a)are used, and then the division is produced. Of course, this process takes only one step. –The rules associated with membranes labelled by hare used for all copies of this membrane. At one step, a membrane can be the subject of only one rule of types (b),(c),(d). In this framework we work without cooperation, without priorities, with cell division rules for elementary membranes, and without changing the labels of membranes. We denote by AM0 −dthe class of all recognizer P systems with active membranes without polarizations and without dissolution. 4 Dependency Graph of a Recognizer P System with Active Membranes Let Πbe a recognizer P systems with active membranes without polarizations and without dissolution. Let Rbe the set of rules associated with Π. Each rule can be considered, in a certain sense, as a dependency between the object triggering the rule and the object or objects produced by its application. We can consider a general format of all kinds of rules of such systems as follows: (a, h)→(a1,h )(a2,h )...(as,h ), according to the following criterion: –The rules of type (a) correspond to the case h=hand s≥1. –The rules of type (b) correspond to the case h=f(h)ands=1. –The rules of type (c) correspond to the case h=f(h)ands=1. –The rules of type (d) correspond to the case h=hand s=2. If his the label of a membrane, then f(h) (respectively, ch(h)) denotes the label of the father (resp. a child) of the membrane labelled by h. We adopt the convention that the father of the skin membrane is the environment. For example, let us consider a general rule (a, h)→(a1,h )(a2,h )...(as,h ). Then we can interpret that from the object ain membrane labelled by hwe can reach the objects a1,...,a sin membrane labelled by h. Next, we formalize these ideas in the following definition. Definition 8. Let Πbe a recognizer P systems with active membranes without polarizations and without dissolution. Let Rbe the set of rules associated with Π. The dependency graph associated with Πis the directed graph GΠ=(VΠ,E Π) defined as follows: VΠ=VL Π∪VR Π, VL Π={(a, h)∈Γ×H:∃u∈Γ∗([a→u]h∈R)∨ ∃b∈Γ([a]h→[] hb∈R)∨ ∃b∈Γ∃h=ch(h)(a[] h→[b]h∈R)∨ ∃b, c ∈Γ([a]h→[b]h[c]h∈R)}, VR Π={(b, h)∈Γ×H:∃a∈Γ∃u∈Γ∗([a→u]h∈R∧b∈alph(u)) ∨ ∃a∈Γ∃h=ch(h)([a]h→[] hb∈R)∨ ∃a∈Γ(a[] h→[b]h∈R)∨ ∃a, c ∈Γ([a]h→[b]h[c]h∈R)}, EΠ={((a, h),(b, h)) : ∃u∈Γ∗([a→u]h∈R∧b∈alph(u)∧h=h)∨ ([a]h→[] hb∈R∧h=f(h)) ∨ (a[] h→[b]h∈R∧h=f(h)) ∨ ∃c∈Γ([a]h→[b]h[c]h∈R∧h=h)}. Proposition 2. Let Πbe a recognizer P systems with active membranes without polarizations and without dissolution. There exists a Turing machine that constructs the dependency graph, GΠ, associated with Π, in polynomial time (that is, in a time bounded by a polynomial function depending on the total number of rules and the maximum length of the rules). Proof. A deterministic algorithm that, given a P system Πwith the set Rof rules, constructs the corresponding dependency graph, is the following: Input: (Π, R) VΠ←∅;EΠ←∅ for each rule r∈Rof Πdo if r=[a→u]h∧alph(u)={a1,...,a s}then VΠ←VΠ∪ s  j=1 {(a, h),(aj,h)};EΠ←EΠ∪ s  j=1 {((a, h),(aj,h))} if r=[a]h→[] hbthen VΠ←VΠ∪{(a, h),(b, f(h))}; EΠ←EΠ∪{((a, h),(b, f(h)))} if r=a[] h→[b]hthen VΠ←VΠ∪{(a, f(h)),(b, h)}; EΠ←EΠ∪{((a, f(h)),(b, h))} if r=[a]h→[b]h[c]hthen VΠ←VΠ∪{(a, h)),(b, h),(c, h)}; EΠ←EΠ∪{((a, h)),(b, h)),((a, h),(c, h))} The running time of this algorithm is bounded by O(|R|·q), where qis the value max{length(r): r∈R}. Proposition 3. Let Π=(Γ, Σ, H, M1,...,Mp,R 1,...,R p,i Π)be a recognizer P systems with active membranes without polarizations and without dissolution. Let ∆Πbe defined as follows: ∆Π={(a, h)∈Γ×H:there exists a path (within the dependency graph) from (a, h)to (yes, environment)} Then, there exists a Turing machine that constructs the set ∆Πin polynomial time (that is, through a polynomial function depending on the total number of rules and the maximum length of the rules). Proof. We can construct the set ∆Πfrom Πas follows: –We construct the dependency graph GΠassociated with Π. –Then we consider the following algorithm: Input: GΠ=(VΠ,E Π) ∆Π←∅ for each (a, h)∈VΠdo if reachability (GΠ,(a, h),(yes, environment)) = yes then ∆Π←∆Π∪{(a, h)} The running time of this algorithm is of the order O(|VΠ|·|VΠ|2), hence it is of the order O(|Γ|3·|H|3). 