Monodirectional P Systems

Monodirectional P Systems? Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy {leporati,luca.manzoni,mauri,porreca,zandron}@disco.unimib.it Summary. We investigate the influence that the flow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these “monodirectional P systems” are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems defined by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space. 1 Introduction P systems with active membranes working in polynomial time are known to be able to solve all PSPACE -complete problems [ 1 ]; this exploits membrane structures of polynomial depth and a bidirectional flow of information (in terms of moving objects or changing charges), both from a parent membrane to its children, and the in opposite direction. When restricting the depth of the membrane structures of a family of P systems to a constant amount, it is still possible to solve problems in the counting hierarchy CH , defined in terms of polynomial-time Turing machines with oracles for counting problems [ 4 ]. In the proof of this result, it has been noticed that send-in communication rules of the form a [ ] α h→ [ b ] β h allow us to check whether the amount of objects located in a membrane exceeds a (possibly exponential) threshold in polynomial time. It is then natural to ask whether that feature is actually necessary in order to obtain the power of counting in polynomial time. In this paper we prove (under the standard complexity-theoretic assumption that PNP 6 = P#P ) that this is actually ? This work was partially supported by Universit`a degli Studi di Milano-Bicocca, FA 2013: “Complessit`a computazionale in modelli di calcolo bioispirati: Sistemi a membrane e sistemi di reazioni”. 208 A. Leporati et al. the case: P systems with monodirectional communication, where the information flows only towards the outermost membrane, are limited to PNP , the class of problems efficiently solved by Turing machines with NP oracles. This happens even when allowing polynomially deep membrane structures, a weak form of nonelementary membrane division, or dissolution (which, in this case, turns out to be as powerful as weak non-elementary division). The PNP upper bound is actually reached when dissolution or weak non-elementary division are allowed; if neither is available, then the computation power decreases to PNP k , where the queries must all be fixed in advance, rather than asked adaptively. Chapter 17 of Papadimitriou’s book [ 7 ] provides more details on complexity classes defined in terms of Turing machines with NP oracles. For an introduction to P systems with active membranes ( AM ), we refer the reader to the original paper by Gh. P˘aun [ 8 ], supplemented by the definitions of complexity classes PMCAM (resp., PMC? AM ) of problems solved by uniform (resp., semi-uniform) families of confluent P systems in polynomial time [ 5 ]. Define M = AM(−i,−n,+wn) to be the class of monodirectional P systems with active membranes, without send-in rules; we also remove the usual (“strong”) non-elementary division rules, of the form [ ]+ h1· · · [ ]+ hm[ ]− hm+1 · · · [ ]− hnα h→[ ]δ h1· · · [ ]δ hmβ h[ ]ζ hm+1 · · · [ ]ζ hnγ h since they also provide a way for membrane h to share information with its children by changing their charge. We replace these rules by “weak” non-elementary division rules [ 11 ] of the form [ a ] α h→ [ b ] β h [ c ] γ h , which allow the creation of complex membrane structures (such as complete binary trees) without exchanging information with the children membranes. Let M(−d) , M(−wn) , and M(−d,−wn) denote monodirectional P systems without dissolution, without weak non-elementary division, and without both kinds of rules, respectively. For each class D of P systems, let PMCD and PMC? D be the classes of problems solvable by uniform and semi-uniform families of P systems of class D. Then, the main results of this paper can be summarised as follows: • The whole class PMC[?] M , as well as PMC[?] M(−d) and PMC[?] M(−wn) , are equivalent to PNP. Here [?] denotes optional semi-uniformity. •The class PMC[?] M(−d,−wn) is equivalent to PNP k. The rest of the paper is structured as follows: in Section 2 we prove some basic limitations of monodirectional P systems; in Section 3 we exploit these results to prove upper bounds to the complexity classes for monodirectional P systems; in Section 4 we provide the corresponding lower bounds by simulating Turing machines with NP oracles; in Section 5 some results of the preceding sections are improved; finally, in Section 6 we present some open problems and directions for future research. Monodirectional P Systems 209 2 Properties of monodirectional P systems We begin by proving some properties of monodirectional P systems that show how the lack of inbound communication substantially restricts the range of behaviours exhibited during the computations. Definition 1. Let Π be a P system, and let C and D be configurations of Π . We say that C is a restriction of D , in symbols C v D , if the membrane structures of the two configurations are identical (i.e., they have the same shape, labelling, and charges) and each multiset of objects of C is a submultiset of that located in the corresponding region of D. The following proposition shows that, while a recogniser P system working in time t might create exponentially many objects per region during its computation, only a polynomial amount (with respect to t ) of them in each region does actually play a useful role if the system is monodirectional: indeed, the final result of the computation can be identified by just keeping track of a number of objects per region equal to the number of steps yet to be carried out. Lemma 1. Let Π be a monodirectional recogniser P system, and let C = ( C0,...,Ct ), with t≥ 1, be a halting computation of Π . Then, there exists a sequence of configurations (D0,...,Dt)such that (i) we have Div Ci for 0 ≤i≤t , and each multiset of Di has at most t−i objects; (ii) for all i<t there exists a configuration Ei+1 such that Ei+1 is reachable in one step from Di(Di→ Ei+1 for brevity) and Di+1 v Ei+1; (iii) a send-out rule of the form [ a ] α h→ [ ] β hyes (resp., [ a ] α h→ [ ] β hno ) is applied to the outermost membrane during the transition step Dt−1→ Et if and only if Cis an accepting (resp., rejecting) computation. Proof. By induction on t . If t = 1, then the environment of C1 contains yes or no , which have been sent out during the computation step C0→ C1 by a rule [ a ] α h→ [ ] β hyes or [ a ] α h→ [ ] β hno . Let D0v C0 be obtained by keeping only the objects on the left-hand side of send-out, dissolution, and division rules applied during C0→ C1 (we call these rules “blocking”, since at most one of them can be applied inside each membrane at each step). At most one object per region is kept, given the lack of send-in rules. Let D1v C1 be obtained by deleting all objects. Then: (i) we have D0v C0 and D1v C1 by construction, and all multisets of D0 and D1 have at most 1 and exactly 0 objects, respectively; (ii) let the transition D0→ E1 be computed by applying all blocking rules applied during the step C0→ C1 , which are all enabled by construction; then E1v C1 and, since D1v C1and D1contains no objects, necessarily D1v E1; (iii) the computation C is accepting if and only if the rule [ a ] α h→ [ ] β hyes is applied from C0 , and the latter is equivalent by construction to that rule being applicable from D0(the reasoning is similar if Cis rejecting). 210 A. Leporati et al. This proves the base case. Now let C = ( C−1,C0,...,Ct ) be a halting computation of length t + 1. The sub-computation ( C0,...,Ct ) is also halting, and by induction hypothesis there exists a sequence of configurations ( D0,...,Dt ) satisfying (i)–(iii). Construct the configuration D−1 as follows: first of all, keep all objects from C−1 that appear on the left-hand side of blocking rules applied during the computation step C−1→ C0 ; this requires at most one object per region, and guarantees that the membrane structure’s shape and charges can be updated correctly (i.e., the same as C0and D0). We must also ensure that all objects of D0 can be generated from D−1 during the transition D−1→ E0 . Once the blocking rules to be applied have been chosen, any object a located inside a membrane of D0 can be traced back to a single object in D−1 . Either a appears on the right-hand side of one of those blocking rules, or it appears on the right-hand side of an object evolution rule applied in the step C−1→ C0 , or it does not appear explicitly in any rule applied in that step; in the latter case, it is either carried on unchanged from D−1 (possibly from another region, if membrane dissolution occurred), or is created by duplicating the content of a membrane by applying a division rule (triggered by a different object). As a consequence, at most t objects per region of D−1 , possibly in conjunction with a single object per region involved in blocking rules, suffice in order to generate the t objects per region of D0. As a consequence, (i) we have D−1v C−1 by construction, and D−1 contains at most t + 1 objects per region; (ii) by applying all blocking rules and as many evolution rules as possible from the computation step C−1→ C0 in D−1 , we obtain a configuration E0 with the same membrane structure as D0 and, as mentioned above, containing all objects from D0(and possibly other objects generated by evolution rules). Since (iii) holds by induction hypothesis, this completes the proof. ut Notice that this lemma does not give us an efficient algorithm for choosing which objects are important for each step of the computation; it only proves that a small (i.e., polynomial-sized) multiset per region exists. However, it is easy to find such an algorithm by slightly relaxing the conditions: instead of limiting the cardinality of the multisets to t−i , we limit the number of occurrences of each symbol to that value, and simply delete the occurrences in excess separately for each symbol. This gives us the larger cardinality bound |Γ| × ( t−i ) per region, which is polynomial whenever the number of computation steps of the system is, and still allows us to simulate the overall behaviour of the P system. Lemma 1 fails for P systems with send-in rules because some configurations where each multiset is small nonetheless require a previous configuration with a region containing exponentially many objects. This is the case, for instance, for P systems solving counting problems, where the number of assignments satisfying a Boolean formula is checked against a threshold by means of send-in rules [ 4 ]. Those assignments are represented in the P system by a potentially exponential number of objects located in the same region, which are sent into exponentially many children Monodirectional P Systems 211 membranes in parallel (i.e., at most one object enters each child membrane), and cannot always be reduced to a polynomial amount without changing the accepting behaviour of the P system. Another property of monodirectional P systems is the existence of computations where membranes having the same labels always have children (and, recursively, all the descendents) with the same configuration. This property will be useful when simulating confluent recogniser monodirectional P systems in Section 3. Lemma 2. Let Π be a monodirectional P system. Then there exists a computation C = ( C0,...,Ct )of Π where, in each configuration Ci , the following holds: any two subconfigurations 2 of Ci having membranes with the same label as roots are identical, except possibly for the multiset and charge of the root membranes themselves. Proof. By induction on i . The statement trivially holds for the initial configuration of Π, since the membranes are injectively labelled. When a division rule is applied to a membrane h , two subconfigurations with root h are created; this is the only way to generate multiple membranes sharing the same label. The two resulting subconfigurations may only differ with respect to the contents and charges of the root membranes, since the internal membranes have evolved before the division of h occurs (recall that the rules are applied, from a logical standpoint, in a bottom-up way [8]). On the other hand, if two subconfigurations with identically labelled root membranes already exist in a configuration Ci , then we can assume that the property holds by induction hypothesis. We can then nondeterministically choose which rules to apply in the subconfiguration having the first membrane as root, excluding the root itself; since the other subconfiguration is identical (except possibly for the root), the same multiset of rules can also be applied to it, thus preserving the property in the next configuration of the system. ut While Lemma 2 somehow “compresses” each level of the configuration of monodirectional P systems, it does not, however, reduce the number of distinct membranes per level to a polynomial number. Indeed, the standard membrane computing technique of generating all (exponentially many) possible assignments to a set of variables does not require send-in rules [ 10 ], and can be carried out in parallel on all levels of the membrane structure. Lemma 2 also fails for P systems with send-in rules. The reason is that two identical subconfigurations can be made different by having a single object located immediately outside, and nondeterministically sending it into one of the root membranes of the two subtrees; the evolution of the two branches of the system might then diverge completely. 2 We define a subconfiguration of Ci as a subtree (a root node together with all its descendents) of the membrane structure of Ci , including labels, multisets, and charges of the membranes. 212 A. Leporati et al. 3 Simulation of monodirectional P systems It is a well-known result in membrane computing that P systems with active membranes can be simulated in polynomial time by deterministic Turing machines if no membrane division rules are allowed [ 10 ]. More specifically, the portion of the system that is not subject to membrane division can be simulated deterministically with a polynomial slowdown, while the output of the dividing membranes can be obtained by querying an appropriate oracle. It was recently proved that, for standard (bidirectional) P systems where only elementary membranes can divide, an oracle for a #P function is necessary and sufficient [5]. In what follows we prove that an NP -oracle is sufficient for the simulation of monodirectional P systems. In particular, the oracle will solve the following problem. Lemma 3. Given the initial configuration of an elementary membrane with label h of a monodirectional P system, an object type a∈Γ , and two integers k, t ∈N in unary notation, it is NP -complete to decide whether the set of membranes with label h existing at time t emits (via send-out or dissolution rules) at least k copies of object aat that time step. Proof. The problem is NP -hard, since one can simulate an arbitrary polynomialtime, nondeterministic Turing machine M by using a single membrane with elementary division (without using send-in rules) and obtain the same result as M by checking if the resulting membranes send out at least one ( k = 1) “acceptance object” at a specific time step [4]. Conversely, the problem can be solved by a nondeterministic, polynomial-time Turing machine M as follows. Simulate t computation steps of the membrane explicitly, by keeping track of its charge and multiset, as in any standard simulation [ 10 ]. If the membrane divides, then M keeps track of all the resulting membranes, until the number exceeds k . If that happens, then k copies of the membrane are chosen nondeterministically among those being simulated (which are at most 2 k after any simulated step, if all membranes divide), and the remaining ones are discarded. Since there is no incoming communication, any instance of the membrane can be simulated correctly, as its behaviour does not depend on the behaviour of its siblings. If one of the simulated membranes dissolves before t steps, one of the k “slots” is released and can be reused in case of a further membrane division. After having simulated t steps as described, the machine M accepts if and only if at least k copies of a are emitted (sent out, or released by dissolution) in the last step by the membranes being simulated. At most k membranes need to be simulated in order to check whether at least k copies of the object are emitted and, by exploiting nondeterminism, we are guaranteed that the correct subset of membranes is chosen by at least one computation of M . Since k and t are polynomial with respect to the size of the input, the result follows. ut Monodirectional P Systems 213 The values of t and k are given in unary since, otherwise, the number of steps or the number of membranes to simulate could be exponential with respect to the size of the input, and the problem would not be solvable in polynomial time. As a consequence of Lemma 3, monodirectional P systems without nonelementary division can be simulated in polynomial time with access to an NP oracle. Theorem 1. PMC? M(−wn) ⊆PNP. Proof. The rules applied to non-elementary membranes can be simulated directly in deterministic polynomial time by a Turing machine M [ 5 ]; this includes the outermost membrane, which ultimately sends out the result object. In order to update the configurations of the non-elementary membranes correctly, the objects emitted from elementary membranes (which potentially divide) have to be added to their multisets. Suppose the P systems of the family being simulated work in polynomial time p ( n ). By Lemma 1, the final result of the computation can be correctly determined by keeping track of at most p ( n ) copies of each object per region. Hence, we can update the configurations by using an oracle for the problem of Lemma 3. At time step t , we make multiple queries for each label h of an elementary membrane and for each object type a∈Γ : by performing a binary search on k over the range [0 , p ( n )], we can find the exact number of copies of a emitted by membranes with label h at time t , or discover that this number is at least p ( n ) (and, in that case, we only add p ( n ) objects to the multiset). This completes the proof. ut Monodirectional P systems without non-elementary division become weaker if dissolution is also disallowed: now a membrane cannot become elementary during the computation, and thus the evolution of each dividing membrane is always independent of the rest of the system. This allows us to perform all queries in parallel, rather than sequentially (in an adaptive way). Theorem 2. PMC? M(−d,−wn) ⊆PNP k. Proof. If dissolution rules are not allowed, being elementary is a static property of the membranes, i.e., a membrane is elementary for the whole computation if and only if it is elementary in the initial configuration. By observing that each query is completely independent of the others (i.e., each query involves a different membrane, time step and object) and also independent of the configurations of the non-dividing membranes (due to the lack of send-in rules), we can perform them in parallel even before starting to simulate the P system. This proves the inclusion in PNP k.ut Now consider monodirectional P systems with non-elementary membrane division. For this kind of systems, the behaviour of a dividing membrane is, of course, dependent on the behaviour of its children and, recursively, of all its descendants. 214 A. Leporati et al. In order to simulate the behaviour of the children by using oracles, we define a more general query problem, where we assume that the behaviour of the descendents of the membrane mentioned in the query has already been established. First of all, notice that the lack of send-in rules allows us to extend the notion of transition step C → D between configurations to labelled subforests 3E of C and F of D as E → F ; the only differences from the standard definition are that E is not necessarily a single tree, and that its outermost membranes may divide and dissolve. Definition 2. Let Π be a monodirectional P system, let C be a configuration of Π , and let h∈Λ be a membrane label. A subforest S of C is called a label-subforest induced by h, or h-subforest for brevity, if one of the following conditions hold: • C is the initial configuration of Π , and S consists of a single tree rooted in the (unique) membrane h, • C is a possible configuration of Π at time t + 1 with C0→ C , and there exists an h-subforest S0in C0such that S0→ S. The notion of h -subforest can be viewed as a generalisation of the equivalence classes of membranes in P systems without charges defined by Murphy and Woods [6]. Lemma 4. Let Π be a monodirectional P system. Then there exists a computation of Π where, at each time step and for each membrane label h∈Λ , all h -subforests are identical. Proof. Multiple h -subforests can only be created by division of an ancestor of h ; but then, by Lemma 2, there exists a computation of Π where the resulting h -subforests are identical. ut Example 1. Figure 1 shows the evolution of the membrane structure of a monodirectional P system and its label-subforests. The label-subforests in the initial configuration C0 coincide with all downward-closed subtrees. In the computation step C0→ C1 both h2 and h3 divide; the division of the latter causes the duplication of the h3 - and h4 -subforests (and, indirectly, of the h5 -subforest); the division of an ancestor membrane is the only way to have more than one label-subforest. By Lemma 4, we can always assume that multiple label-subforests induced by the same label are identical. In the computation step C1→ C2 , the rightmost membrane having label h2 and both instances of h4 dissolve. Notice that this does not cause the disappearance of the two h4 -subforests: in the general case, the membranes h4 might contain label-subforests induced by different labels, and we still need to refer to them as a single entity (the h4 -subforest), without the need to describe the internal structure, even when h4ceases to exist. As can be observed from Figure 1, a subforest can be identified as an h -subforest by checking whether it can be generated from the downward-closed subtree rooted in hin the initial configuration. 3 We define a subforest F0 of a forest F to be any subgraph such that, whenever F0 includes a vertex v, it also includes all the descendents of v. Monodirectional P Systems 215 h1 h2 h4 h5 h2 h4 h5 h1 h2 h3 h4 h5 h3 h3h3 h3 h1 h2 h3 h3h3 h3 h4 h5 h4 h5 C0C1 C2 Fig. 1. Evolution of a membrane structure and its label-subforests, which are enclosed by dashed rectangles. A computation that ensures that all h -subforests are identical for all h∈Λ can be obtained by imposing a total ordering (a priority) on the set of rules of the P system, and applying inside each membrane the rules with higher priority whenever possible. In the following, we assume that a priority order (e.g., the lexicographic order) has been fixed; there is no loss of generality in doing that, since we only focus on confluent P systems in this paper. We define the multiset of objects emitted by a label-subforest as the union of the multisets emitted by its outermost membranes. Lemma 5. Given the initial configuration of a membrane with label h of a monodirectional P system, an object a∈Γ , two integers k, t ∈N in unary notation, and a table T of the objects emitted during computation steps 1 , . . . , t by the label-subforests immediately contained in h , it is NP -complete to decide whether each h -subforest emits at least kcopies of object aat time t. 222 A. Leporati et al. Theorem 4. A deterministic polynomial-time Turing machine which asks p ( n ) queries to an NP oracle on inputs of length n can be simulated by a uniform family of monodirectional P systems of depth p ( n )without non-elementary division rules. Proof. The family of P systems Π = {Πx : x∈ { 0 , 1 }?} simulating M on input x can be constructed uniformly in polynomial time, since only the initial multiset depends on the actual string x , while the set of rules and the membrane structure only depend on |x| . We only need to make sure that the indices of the tape-objects are large enough to ensure that both the tape of M and the tape of M0 can be represented at the same time. ut Corollary 1. PNP ⊆PMCM(−wn).ut Instead of using membrane dissolution as in rule (23) , we can use the object ˆq0 ! to produce ⊕: [ˆq0 !→ ⊕]α hfor α∈ {+,−} (26) which ensures that the charge of h is positive instead of negative two steps later. The tape-objects are then sent out, one at a time, by using the following rules: [1i]+ h→[ ]+ h1ifor −(m−1) ≤i≤m−1 (27) The timer t of the object ˜q!,t has to be increased appropriately, in order to take into account the time needed to send out all the tape-objects. However, since the membrane where the simulation of M is non-elementary after the first query, rule (20) is now a weak non-elementary division rule. As a consequence, we have: Theorem 5. A deterministic polynomial-time Turing machine which asks p ( n ) queries to an NP oracle on inputs of length n can be simulated by a uniform family of monodirectional P systems of depth p(n)without dissolution rules. ut Corollary 2. PNP ⊆PMCM(−d).ut In order to prove the converse of Theorem 2, we introduce an auxiliary complexity class (a variant of the class of optimisation problems OptP [3]). Definition 3. Define OrP to be the class of functions f:{ 0 , 1 }?→ { 0 , 1 }? having a polynomial-time nondeterministic Turing machine M such that, for all x∈ { 0 , 1 }? , we have f ( x ) = WM ( x ), where M ( x )denotes the set of possible output strings of M on input x , and W denotes bitwise disjunction of strings; here we assume that the bitwise disjunction of strings of different lengths is performed by padding the shortest ones with zeros. The purpose of the class OrP is to capture a polynomial number of parallel NP queries with a single query to a function over binary strings. Proposition 1. PNP k=POrP[1]. Monodirectional P Systems 223 Proof. A polynomial number of parallel queries y1, . . . , ym to an oracle for L∈NP can be replaced by a single query to an oracle for the function f ( y1, . . . , ym ) = z1· · · zm , where zi = 1 if and only if yi∈L . Let M be an NP machine deciding L , and let M0 be the following nondeterministic machine: on input y1, . . . , ym simulate M on each yi and record the corresponding output bit zi ; finally, output z1· · · zm . For all 1 ≤i≤m , if yi is accepted by the oracle, then there exists a computation of M0 such that zi = 1: thus, by taking the bitwise disjunction of all possible output strings of M0 , we obtain the i -th bit of f ( y1, . . . , ym ); this proves that f∈OrP . Notice that this proof requires the query strings y1, . . . , ym to be fixed in advance, i.e., the queries cannot be performed adaptively. Vice versa, a single query to an oracle for f∈OrP with query string y can be replaced by the following polynomial number of parallel queries, one for each 1 ≤i≤ |f ( y ) | : “is the i -th bit of f ( y ) a 1?”. These queries are in NP , since they can be answered by simulating an OrP machine M for f and selecting only its i -th output bit; the answer will be positive if and only if there exists a computation of M having a 1 as the i -th output bit, which (by definition of OrP ) is equivalent to the i-th bit of f(y) being 1. ut Simulating an OrP query by means of a P system is completely analogous to simulating an NP query, except that, instead of a single output bit, we have a polynomial number of them. These binary strings are automatically combined by bitwise disjunction when the tape-objects are sent out of the membrane simulating the nondeterministic Turing machine. Furthermore, since a single OrP query suffices to capture PNP k, we obtain the following results: Theorem 6. A deterministic polynomial-time Turing machine which asks a polynomial number of parallel queries to an NP oracle on inputs of length n can be simulated by a uniform family of monodirectional P systems of depth 1 without dissolution (and, necessarily, without non-elementary division). ut Corollary 3. PNP k⊆PMCM(−d,−wn).ut 5 Further results The depth of the P systems of Theorems 4 and 5 can be asymptotically reduced by exploiting the equivalence of a logarithmic number of adaptive queries and a polynomial number of parallel queries [ 7 , Theorem 17.7], formally PNP k = PNP[log n] . Suppose a deterministic polynomial-time Turing machine performs p ( n ) sequential NP queries, and divide these queries into Θ ( p ( n ) /log n ) blocks of Θ ( log n ) queries. Each block can then be replaced by a polynomial number of parallel NP queries or, by Proposition 1, by a single OrP query. Hence, p ( n ) sequential NP queries can be simulated by Θ ( p ( n ) /log n ) sequential OrP queries, and each of the latter can be simulated by one level of depth in a P system: 224 A. Leporati et al. Corollary 4. A deterministic polynomial-time Turing machine which asks p ( n ) queries to an NP oracle on inputs of length n can be simulated by a uniform family of monodirectional P systems of depth Θ ( p ( n ) /log n )without non-elementary division rules (resp., without division rules). ut Theorem 3 can be sharpened by making the intra-level query parallelism explicit with OrP queries: Corollary 5. Let Π be a family of semi-uniform polynomial-time monodirectional P systems of depth f ( n ). Then Π can be simulated by a polynomial-time deterministic Turing machine with f(n)queries to an OrP oracle. ut We can also prove that monodirectional families of P systems of any constant depth, even with dissolution and non-elementary division rules (in symbols M(O(1)) ), are always equivalent to families of depth one without dissolution and without non-elementary division (in symbols M(1,−d,−wn) ), and thus only able to simulate parallel NP queries. Theorem 7. PMC[?] M(O(1)) =PMC[?] M(1,−d,−wn) =PNP k. Proof. By Theorem 6, we already know that PNP k⊆PMCM(O(1)) , even when limited to depth 1; the inclusion PMCM(O(1)) ⊆PMC? M(O(1)) holds by definition. The inclusion PMC? M(O(1)) ⊆PNP k can be proved as follows. By Theorem 3, a family of P systems of constant depth k can be simulated in polynomial time by asking k sets (one per level) of p ( n ) parallel queries, for some polynomial p . Each set of p ( n ) parallel queries can be converted into Θ ( log n ) sequential queries [ 7 , Theorem 17.7], for a total of k×Θ ( log n ) sequential queries. These can be converted back into a polynomial number of parallel queries. ut Finally, observe that Theorem 3 also trivially holds for monodirectional P systems without charges. This implies a better upper bound than previously known [ 5 ] for a monodirectional variant of the P conjecture [ 9 , Problem F], which states that P systems without charges and without non-elementary division characterise P. 6 Conclusions In this paper we confirmed the importance of the direction of the information flow in P systems with active membranes with respect to their computing power. Indeed, when working in polynomial time and using only outward-bound communication, the corresponding complexity class decreases from PSPACE to PNP , or from P#P to PNP k when non-elementary division and dissolution rules are disallowed. It is interesting to notice that, unlike with other restrictions such as removing membrane division [ 10 ] or charges and dissolution [ 2 ], the resulting P systems are still more powerful than P(unless, of course, P=NP). Monodirectional P Systems 225 The role of strong non-elementary division (which is replaced in this paper by weak non-elementary division) in the absence of send-in rules is still unclear. Even if it provides a way to convey information from a parent membrane to its children, we do not know whether this is sufficient to altogether replace send-in communication while maintaining a polynomial run-time. Finally, it would be interesting to investigate monodirectional P systems where the information flow is reversed, i.e., send-out communication and dissolution rules (as well as strong non-elementary division rules) are disallowed. A first issue to overcome is choosing an appropriate acceptance condition for the P systems, to replace sending out yes or no from the outermost membrane. The acceptance condition most similar “in spirit” to the original one is probably accepting (resp., rejecting) by having at least one yes (resp., no ) object appear, either anywhere in the system, or inside a distinguished (and possibly dividing) membrane, during the last computation step; we also add the restriction that yes and no can never appear together, since giving the priority to one of them would allow us to solve NP - complete (or coNP -complete) problems “for free”. Such monodirectional P systems appear to be very weak when working in polynomial time; indeed, even though exponentially many membranes can still be created by division, they can never communicate. Is P actually an upper bound to the class of problems they can solve? References 1. Alhazov, A., Mart´ın-Vide, C., Pan, L.: Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae 58(2), 67–77 (2003) 2. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Riscos-Nu˜nez, A., Romero-Campero, F.J.: Computational efficiency of dissolution rules in membrane systems. International Journal of Computer Mathematics 83(7), 593–611 (2006) 3. Krentel, M.W.: The complexity of optimization problems. Journal of Computer and System Sciences 36, 490–509 (1988) 4. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Membrane division, oracles, and the counting hierarchy. Fundamenta Informaticae (2015), in press 5. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Simulating elementary active membranes, with an application to the P conjecture. In: Gheorghe, M., Rozenberg, G., Sos´ık, P., Zandron, C. (eds.) Membrane Computing, 15th International Conference, CMC 2014, Lecture Notes in Computer Science, vol. 8961, pp. 284–299. Springer (2015) 6. Murphy, N., Woods, D.: Active membrane systems without charges and using only symmetric elementary division characterise P. In: Eleftherakis, G., Kefalas, P., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, 8th International Workshop, WMC 2007. Lecture Notes in Computer Science, vol. 4860, pp. 367–384 (2007) 7. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1993) 8. P˘aun, Gh.: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001) 226 A. Leporati et al. 9. P˘aun, Gh.: Further twenty six open problems in membrane computing. In: Gut´ıerrez- Naranjo, M.A., Riscos-Nu˜nez, A., Romero-Campero, F.J., Sburlan, D. (eds.) Proceedings of the Third Brainstorming Week on Membrane Computing. pp. 249–262. F´enix Editora (2005) 10. Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, UMC’2K, Proceedings of the Second International Conference, pp. 289–301. Springer (2001) 11. Zandron, C., Leporati, A., Ferretti, C., Mauri, G., P´erez-Jim´enez, M.J.: On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae 87, 79–91 (2008)