On a partial affirmative answer for a Paun's Conjecture

December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 ON A PARTIAL AFFIRMATIVE ANSWER FOR A P˘ AUN’S CONJECTURE IGNACIO P´ EREZ-HURTADO, MARIO J. P´ EREZ-JIM´ ENEZ, AGUST´ IN RISCOS-N´ U˜ NEZ and MIGUEL A. GUTI´ ERREZ-NARANJO Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {magutier,perezh,marper,ariscosn}@us.es http://www.gcn.us.es MIQUEL RIUS-FONT Department of Applied Mathematics IV, Universitat Polit´ecnica de Catalunya Edifici C3, Despatx 016, Av. del Canal Ol´ımpic, s/n, 08860 Castelldefels, Spain [email protected]c.edu Received 21 June 2010 Accepted 30 September 2010 Communicated by Victor Mitrana At the beginning of 2005, Gheorghe P˘aun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for elementary membranes), polarizations cannot be avoided in order to solve computationally hard problems efficiently (assuming that P6=NP). At the middle of 2005, a partial positive answer was given, proving that the conjecture holds if dissolution rules are forbidden. In this paper we give a detailed and complete proof of this result modifying slightly the notion of dependency graph associated with recognizer P systems. Keywords: Polarizationless P systems; active membranes; dissolution rules; computational complexity; tractability. 1. Preliminaries The present work is developed within the framework of polarizationless P systems with active membranes where division rules can only be applied to elementary membranes. In order to make this paper selfcontained, let us introduce next the required concepts. 1.1. Notations Let us recall that an alphabet Γis a nonempty set and a string on Γis a finite sequence of elements of Γ. The set of symbols ocurring in a string wis denoted by alph(w). We denote by Γ∗the set of all strings over Γ. A language over Γis a subset of Γ∗. 55 December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 56 I. P´erez-Hurtado et al. A multiset over an alphabet Γis a map from Γinto the set of natural numbers, N. The support of a multiset fover Γis supp(f) = {a∈Γ : f(a)>0}. If f, g are multisets over Γ, then we define the union or sum of fand gas follows: the multiset f+gdefined by (f+g)(a) = f(a) + g(a), for each a∈Γ. Adecision problem,X, is a pair (IX, θX)such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function (that is, a predicate) over IX. Given a decision problem X= (IX, θX)we can associate a language to it as follows: LX={w∈IX:θX(w) = 1}. Conversely, given a language L, over an alphabet Γ, we can associate a decision problem to it as follows: XL= (IXL, θXL), where IXL= Γ∗, and θXL={(x, 1) : x∈L} ∪ {(x, 0) : x /∈L}. In this paper we work only with finite alphabets. 1.2. The graph reachability problem and the circuit value problem The graph reachability (or accessibility) problem is the following: given a directed graph, G= (V, E), with two specified vertices sand t, determine whether or not there is a path from sto t. We denote this decision problem by REACHABILITY. There are algorithms solving this problem, for instance, search algorithms based on breadth first search or depth-first search. These algorithms determine whether two vertices are connected in O(max(|V|,|E|)) time. Moreover, they basically need to store at most |V|items, so these algoritms use O(|V|)space. But this quantity of space can be reduced to O(log2|V|)by using an algorithm that could be called middle-first search (see [2]for details, pp. 149-150). In particular, REACHABILITY ∈P. The circuit value problem is the following: given a circuit with no variable gates and where each input gate has an associated boolean value, determine whether or not the circuit evaluates to True. It is well known that the circuit value problem is a P–complete problem (see theorem 8.1 in [2]for details). 1.3. Polarizationless P system with active membranes Definition 1. Apolarizationless P system with active membranesof degree q≥1is a tuple Π = (Γ, H, µ, M1,...,Mq, R, houtput), where: (1) Γis a working alphabet of objects, and His a finite set of labels for membranes; (2) µis a membrane structure (a rooted tree) consisting of qmembranes injectively labeled with elements of H, the label of membrane iis denoted by l(i); (3) M1,...,Mqare strings over Γdescribing the multisets of objects placed in the q initial regions of µ; (4) Ris a finite set of developmental rules, of the following forms: (a) [a→u]h, for h∈H,a∈Γ,u∈Γ∗(object evolution rules). (b) a[ ]h→[b]h, for h∈H,a, b ∈Γ(send–in communication rules). (c) [a]h→[ ]hb, for h∈H,a, b ∈Γ(send–out communication rules). (d) [a]h→b, for h∈H,a, b ∈Γ(dissolution rules). December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 On a Partial Affirmative Answer for a P˘aun’s Conjecture 57 (e) [a]h→[b]h[c]h, for h∈H,a, b, c ∈Γ (division rules for elementary membranes. (5) houtput ∈Hor houtput =env (env is the label of the environment) indicates the output region. These rules are applied according to usual principles of polarizationless P systems (see [4]for details). Notice that in this polarizationless framework there is no cooperation, nor priority, nor changes of the labels of membranes. In this paper we do not consider division rules for non-elementary membranes. A membrane structure is a rooted tree. Thus, we can define the notion of the father f(h)or a child ch(h)of a region labeled by hin a natural manner. The length of a rule is the number of symbols ocurring in it. For instance, communication and dissolution rules have length 2, but division rules have length 3. In order to solve decision problems in the so-called uniform way we will work with P systems with input membrane. These systems have an input alphabet Σstrictly contained in the working alphabet Γ, the initial multisets are over Γ\Σ, and they also have a distinguished membrane (the input membrane) in which the instances of a problem are encoded by multisets over the input alphabet Σ. Specifically, if Π = (Γ,Σ, H, µ, M1,...,Mq, R, houtput, hinput), and IM ∈Σ∗then the initial configuration of Πwith input IM is (M1,...,Minput +IM,...,Mq). Usually, we write Π + IM. Let us recall that in recognizer P systems, the working alphabet contains two distinguished elements yes and no, the output of the system is collected in the environment, all computations halt, and if Cis a computation of the system, then either object yes or object no (but not both) must have been sent to the output region of the system, and only at the last step of the computation. Without loss of generality, we can suppose that in a recognizer P system with active membranes Π, for each label h∈Hthe number of rules associated with membrane his lower than or equal to 2· |Γ|(the non-determinism among all the rules associated with a given membrane, except those of send-in type, can be avoided). Thus, we can suppose that |RΠ| ≤ 2q· |Γ|, where qis the degree of Π. The class of recognizer polarizationless P systems with active membranes (resp., which do not make use of division rules) is denoted by AM0(resp., N AM0). If we consider three electrical charges the correspondingclasses are denoted by AM and NAM, respectively. We also denote by AM0(−d)the class of all recognizer P systems with polarizationless active membranes such that dissolution rules are forbidden. Definition 2. A decision problem X= (IX, θX)is solvablein polynomial time by a family of recognizer P systems with input membrane Π={Π(n) : n∈N}, denoted by X∈ PMCR, if the following holds: •There exists a deterministic Turing machine (DTM) working in polynomial time which constructs the system Π(n)from n∈N. •There exists a pair (cod, s)of polynomial time computable functions over IX(a polynomial encoding of Xin Π) such that for each instance w∈IX,s(w)is a natural December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 58 I. P´erez-Hurtado et al. number (obtained by means of a reasonable encoding scheme) and cod(w)is an input multiset of the system Π(s(w)). •There exists k∈Nsuch that for each instance w∈IX, every computation of the system Π(s(w)) with input cod(w)performs at most |w|ksteps. •For each instance, w∈IX: (a) if there exists an accepting computation of Π(w), then θX(w) = 1; and (b) if θX(w) = 1, then every computation of Π(w)is an accepting computation. The family Πis said to provide a (polynomial–time) uniform solution to the problem X. As a direct consequence of working with recognizer membrane systems, these complexity classes are closed under complement. Moreover, they are closed under polynomial time reductions [7]. The proof of the Milano theorem [9](each deterministic P system with active membranes but without membrane division can be simulated by a deterministic Turing machine with a polynomial slowdown) and a proof given by A.E. Porreca [8](each tractable problem can be solved in polynomial time by families of recognizer P systems with active membranes and without input) can be adapted in order to show the following result: Corollary 3. PMCN AM0=P. This result suggests the following question: whether in the framework of polarizationless P systems with active membranes, division rules (only for elementary membranes) provide a borderline between tractability and intractability (assuming that P6=NP). Let us recall that P⊆PMCT, where Tis the class of all basic transition P systems (that is, transition P systems with only evolution, communication, and dissolution rules). In this kind of P systems the size of the membrane structure does not increase. The proof of this result can also be adapted to prove PMCN AM =P. It is well known that computationally hard problems can be solved in a uniform way by families of P systems from AM. Therefore, in the framework of P systems with active membranes and three electrical charges, division rules (only for elementary membranes) provide a borderline between tractability and intractability (assuming that P6=NP). 2. A Conjecture of P˘ aun At the beginning of 2005, Gh. P˘aun (problem Ffrom [5]) wrote: My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible – and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non–efficiency to efficiency. This so–called P˘aun’s conjecture can be formally formulated in terms of membrane computing complexity classes as follows: P=PMCAM0. An affirmative answer to the conjecture would indicate that the ability to create an exponential amount of workspace (expressed in terms of the number of membranes and December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 On a Partial Affirmative Answer for a P˘aun’s Conjecture 59 objects) in polynomial time, is not enough in order to solve computationally hard problems efficiently. Conversely, a negative answer to the conjecture would provide a borderline between tractability and intractability (assuming that P6=NP): division rules for elementary membranes. In this paper we provide a partial affirmative answer of the P˘aun’s conjecture in the case that dissolution rules are forbidden. The proof of this result is based on the concept of dependency graph, improving and formalizing the result presented in [1]. Let Πbe a recognizer polarizationless P system with active membranes which do not make use of dissolution rules. A directed graph can be associated with Πverifying the following property: every accepting computation of Πis characterized by the existence of a path in the graph between two specific nodes. Definition 4. Let Π = (Γ, H, µ, M1,...,Mq, RΠ, env), be a recognizer P system with active membranes without polarizations and without dissolution. The dependency graph associated with Πis the directed graph GΠ= (VΠ, EΠ)defined as follows: VΠ=V LΠ∪V RΠ∪ {sΠ},sΠ/∈Γ∪H, V LΠ={(a, h)∈Γ×H:∃u∈Γ∗([a→u]h∈RΠ)∨ ∃b∈Γ ([a]h→[ ]hb∈RΠ)∨ ∃b∈Γ∃h0∈ch(h) (a[ ]h0→[b]h0∈RΠ)∨ ∃b, c ∈Γ ([a]h→[b]h[c]h∈RΠ))}, V RΠ={(b, h)∈Γ×H:∃a∈Γ∃u∈Γ∗([a→u]h∈RΠ∧b∈alph(u)) ∨ ∃a∈Γ∃h0∈ch(h) ([a]h0→[ ]h0b∈RΠ)∨ ∃a∈Γ (a[ ]h→[b]h∈RΠ)∨ ∃a, c ∈Γ ([a]h→[b]h[c]h∈RΠ∨[a]h→[c]h[b]h∈RΠ)}, EΠ=E1 Π∪E2 Π, E1 Π={(sΠ,(a, h)) : the object ais in membrane hat the initial configuration of Π}, E2 Π={((a, h),(b, h0)) : ∃u∈Γ∗([a→u]h∈RΠ∧b∈alph(u)∧h=h0)∨ ([a]h→[ ]hb∈RΠ∧h0=f(h)) ∨ (a[ ]h0→[b]h0∈RΠ∧h=f(h0)) ∨ ∃c∈Γ (([a]h→[b]h[c]h∈RΠ∨[a]h→[c]h[b]h∈RΠ)∧h=h0)}. December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 60 I. P´erez-Hurtado et al. This definition modifies the Definition 10 from [1]slightly. Bearing in mind that in recognizer P systems all computationshalt, we deduce that each path in the dependency graph associated with it must be simple. Proposition 5. There exists a deterministic Turing machine working in polynomial time that construct the dependency graph associated with each recognizer P system with active membranes without polarizations and without dissolution. Proof. A deterministicalgorithm that given a recognizerP system constructs the associated dependency graph, is the following: Input: Π = (Γ, H, µ, M1,...,Mq, RΠ, env)∈ AM0(−d) VΠ← {sΠ};EΠ← ∅ for i←1to qdo for each a∈supp(Mi)do VΠVΠ∪ {(a, l(i))};EΠEΠ∪ {(sΠ,(a, l(i)))} for each rule r∈RΠdo if r= [a→u]h∧alph(u) = {a1, . . . , as}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 of the order O(q· |RΠ|+m· |RΠ|), where qis the degree of the P system Π, and mis the value max{length(r) : r∈RΠ}. As |RΠ| ≤ 2q· |Γ|, the total cost time of the algorithm is O((q+m)·q· |Γ|). Next, let us prove that the dependency graph associated with a P system from AM0(−d) can be used to characterize the behavior of the system (accepting or rejecting inputs), through the analysis of simple paths. Theorem 6. Let Π = (Γ, H, µ, M1, . . . , Mq, RΠ, env)be a recognizer P system from AM0(−d). The following assertions are equivalent: (1) There exists an accepting computation of Π. December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 On a Partial Affirmative Answer for a P˘aun’s Conjecture 61 (2) There exists a simple path in the dependency graph GΠfrom sΠto (yes, env)with length greater or equal to 2. Proof. In order to prove that (1) =⇒(2) we will see that for each n≥1and for each computationC= (C0, C1,...,Cn)of Π, if Cis an accepting computation,then there exists a simple path in the dependency graph GΠfrom sΠto (yes, env). By induction on i. If C= (C0, C1)is an accepting computation of Π, then at the only step of that computation, the object yes has been sent to in the environment by a rule of the form [a]hs→yes [ ]hs, where hsis the label of the skin membrane. Of course, in order to apply the rule, object amust occur in the skin in the initial configuration. Thus ((sΠ,(a, hs),((a, hs),(yes, env)) is a simple path in GΠfrom sΠto (yes, env)with length greater or equal than 2. That is, the result holds for n= 1. Let n≥1and let us suppose that the result holds for n. Let C= (C0, C1,...,Cn, Cn+1)be an accepting computation of Π. Let us consider the recognizer P system Π0= (Γ, H, µ, M0 1,...,M0 q, RΠ, env)where for each i,1≤i≤q,M0 iis the contents of region iin the configurationC1. Then C0= (C1,...,Cn, Cn+1)is an accepting computation of Π0of length n. By the induction hypothesis, there exists a simple path γ0 in the dependency graph GΠ0from sΠ0to (yes, env)with length greater or equal than 2. Let (a1, h1)the next vertex of sΠ0in that path. Then, the object a1belongs to the region i labeled by h1in the configuration C1. We consider two cases: – The object a1is in region labeled by h1in the configuration C0. In this case, substituting the vertex sΠ0by sΠin γ0we obtain a simple path in the dependency graph GΠfrom sΠto (yes, env)with length greater or equal than 2. – The object a1is not in region labeled by h1in the configuration C0. In this case, the pair (a1, h1)has been produced at the first step of the computation C, that is, there exist (a0, h0)∈Γ×Hand a rule r∈RΠsuch that by applying rthe pair (a0, h0)produces (a1, h1). Hence, ((sΠ,(a0, h0)),((a0, h0),(a1, h1)), γ0− {(sΠ0,(a1, h1))}) is a simple path in the dependencygraph GΠfrom sΠto (yes, env)with length greater or equal than 2. In order to prove that (2) =⇒(1) we will see that for each n≥2and for each simple path γin the dependency graph GΠfrom sΠto (yes, env)with length n, there exists an accepting computation of Π. Let us reason again by induction on i. In the base case, let γbe a simple path in GΠ from sΠto (yes, env)with length 2. Then, there exists an object a0in a region labeled by h0in the initial configuration such that γ= ((sΠ,(a0, h0)),((a0, h0),(yes, env))). Let C1a configuration obtained from C0by applying a rule of Πthat yields (yes, env)from (a0, h0)(of course, many other rules could be applied at the same step in a maximally parallel way). Then, C= (C0, C1)is an accepting computation of Π. Let n≥2and let us suppose that the result holds for n. Let γ= ((sΠ,(a0, h0)),((a0, h0),(a1, h1)),...,((an−1, hn−1),(yes, env))) December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 62 I. P´erez-Hurtado et al. be a simple path in GΠfrom sΠto (yes, env)with length n+ 1. For each j,j= 0,1,...,n−1, we denote by rja rule of Πtransforming (aj, hj)into (aj+1, hj+1), where an=yes and hn=env. Let C1a configuration obtained from the initial configuration C0from Πby applying a multiset of rules containing r0. Let Π0be the recognizer P system: Π0= (Γ, H, µ, M0 1,...,M0 q, RΠ, env) where for each i,1≤i≤q,M0 iis the contents of region iin the configuration C1. Then, γ0= ((sΠ0,(a1, h1)),((a1, h1),(a2, h2)),...,((an−1, hn−1),(yes, env))) is a simple path in GΠ0from sΠ0to (yes, env)with length n. From the induction hypothesis we deduce that there exists an accepting computation C0= (C1, C2,...,Ct)of Π0. Therefore, C= (C0, C1, C2,...,Ct)is an accepting computation of Π. Corollary 7. Let X= (IX, θX)be a decision problem. Let Π={Π(n) : n∈N} be a family of recognizer P systems from AM0(−d)solving Xin a uniform way and in polynomial time. Let (cod, s)be a polynomial encoding associated with that solution. Then, for each instance w∈IXthe following assertions are equivalent: (1) θX(w) = 1. (2) There exists a simple path in the dependency graph associated with Π0= Π(s(w)) + cod(w), from sΠ0to (yes, env). Proof. It is enough to take into account the previoustheorem and to notice that θX(w) = 1 if and only if there exists an accepting computation in the system Π(s(w)) with input multiset cod(w). Theorem 8. PMCAM0(−d)=P. Proof. Let us notice that P⊆PMCAM0(−d)because the class PMCAM0(−d)is closed under polynomial–time reduction and contains the P–complete problem CIRCUIT VALUE. Let us see the converse inclusion. Let X∈PMCAM0(−d). Let Π={Π(n) : n∈N} be a family of recognizer P systems from AM0(−d)solving Xin a uniform way and in polynomial time. Let (cod, s)be a polynomial encoding associated with that solution. Let us see that X≤pREACHABILITY. Let wbe an instance of X. Let us consider the system Π(s(w)) with input multiset cod(w). Then we define: F(w) = (GΠ(s(w))+cod(w), sΠ(s(w))+cod(w),(yes, env)) From Proposition 5we deduce that Fis a polynomial–time computable function. Moreover, we have: w∈LX⇐⇒ θX(w) = 1 Cor.7 ⇐⇒ F(w)∈LREACHABILITY December 28, 2010 12:24 WSPC/INSTRUCTION FILE S0129054111007824 On a Partial Affirmative Answer for a P˘aun’s Conjecture 63 Finally, we deduce that X∈Pbecause of the class Pis closed under polynomial–time reductions, X≤pREACHABILITY and REACHABILITY ∈P. Therefore, the feeeling expressed by Gh. P˘aun on his conjecture could be reformulated as follows: in the framework on polarizationless P systems with active membranes, passing from allowing dissolution rules to forbidding them amounts to passing from non-efficiency to efficiency (assuming that P6=NP). 3. Conclusions Dissolution rules can be avoided when we solve NP–complete problems in an uniform way and in polynomial time by families of P systems with active membranes and three electrical charges [6]. This paper is partially answering a conjecture formulated by Gheorghe P˘aun at the beginning of 2005 related with the role played by the polarizations in the framework of P systems with active membranes from a computationalcomplexity point if view. We present a detailed proof of a partial affirmative answer that highlights the relevance (in AM0)of an apparently innocent ingredient: dissolution rules. Acknowledgments The authors acknowledge the support of the project TIN2009–13192 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds, and the support of the Project of Excellence with Investigador de Reconocida Val´ ıa of the Junta de Andaluc´ıa, grant P08- TIC-04200. References [1] M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, F.J. Romero-Campero. On the power of dissolution in P systems with active membranes. In R. Freund, Gh. Paun, Gr. Rozenberg, A. Salomaa (eds.) Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 3850 (2006), 224-240. [2] Ch. H. Papadimitriou. Computational Complexity, Addison-Wesley, California, USA, 1995. [3] Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), pp. 108–143, and Turku Center for Computer Science-TUCS Report No 208. [4] Gh. P˘aun. P systems with active membranes: Attacking NP–complete problems. Journal of Automata, Languages and Combinatorics,6, 1 (2001), 75–90. [5] Gh. P˘aun. Further twenty six open problems in membrane computing. In M.A. Guti´errez, A. Riscos, F.J. Romero, D. Sburlan (eds.) Proceedings of the Third Brainstorming Week on Membrane Computing, Report RGNC 01/04, F´enix Editora, Sevilla, 2005, pp. 249–262. [6] M.J. P´erez–Jim´enez, A. Romero–Jim´enez, F. Sancho–Caparrini. Complexity classes in cellular computing with membranes. Natural Computing,2, 3 (2003), 265–285. [7] M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 11, 4 (2006), 423-434. A preliminary version in E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszil (eds.) Proceedings of the Fifth International Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, Budapest, Hungary, July 12-14, 2003, pp. 284-294.