On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution Claudio Zandron1, Alberto Leporati1, Claudio Ferretti1, Giancarlo Mauri1, Mario J. P´erez-Jim´enez2 1Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano – Bicocca Viale Sarca 336/14, 20126 Milano, Italy E-mails: {zandron,leporati,ferretti,mauri}@disco.unimib.it 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] Summary. Recognizer P systems with active membranes have proven to be very powerful computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-sat by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximal parallel way. 1 Introduction Membrane systems (also known as P systems) have been introduced in [11] as a parallel, nondeterministic, synchronous and distributed model of computation inspired by the structure and functioning of living cells. The basic model consists of a hierarchical structure composed by several membranes, embedded into a main membrane called the skin. Membranes divide the Euclidean space into regions, that contain some objects (represented by symbols of an alphabet) and evolution rules. Using these rules, the objects may evolve and/or move from a region to a neighboring one. Usually, the rules are applied in a nondeterministic and maximally parallel way; moreover, all the objects that may evolve are forced to evolve. A computation starts from an initial configuration of the system and terminates 262 C. Zandron et al. when no evolution rule can be applied. The result of a computation is the multiset of objects contained into an output membrane, or emitted from the skin of the system. An interesting subclass of membrane system is constituted by recognizer P systems, in which: (1) all computations halt, (2) only two possible outputs exist (usually named yes and no), and (3) the result produced by the system depends only upon its input, and is not influenced by the particular sequence of computation steps taken to produce it. For a systematic introduction on P systems we refer the reader to [14], whereas the latest information can be found in [24]. Since the introduction of membrane systems, many investigations have been performed on their computational properties: in particular, many variants have been proposed in order to study the contribution of various ingredients (associated with the membranes and/or with the rules of the system) to the achievement of the computational power of these systems. In this respect, it is known [19, 23, 5] that the class of all decision problems which can be solved in polynomial time by a family of recognizer P systems that use only basic rules, that is, evolution, communication and rules involving membrane dissolution, coincides with the standard complexity class P. Hence, in order to efficiently solve NP-complete problems by means of P systems it seems necessary to be able to construct an exponential workspace, expressed by the number of membranes, in polynomial time. In particular, two features have proven to be of paramount importance in establishing whether a membrane system is able to solve NP-complete decision problems in polynomial time: membrane division and dissolution. The former is inspired from the biological process called mitosis: using division rules we can duplicate a given membrane that contains one specified symbol, possibly rewriting this symbol in a different way in each of the cells produced by the process. All the other symbols, as well as the rules, which are contained in the original cell are copied unaltered into each of the resulting cells. As for the membranes eventually contained in the original cell, we can make the following distinctions. If no membrane occurs, the we say that the division is elementary; if at least one membrane occurs, then the division is non elementary, and we have to specify how the membranes are distributed to the resulting membranes. If all the membranes are copied to each of the resulting membranes, then we have a weak (non-elementary) division; if, on the other hand, we can choose what membranes are copied into each of the resulting membranes, then we have strong (non-elementary) division. Membrane dissolution is performed by rules that simply dissolve the surrounding membrane when a specified symbol occurs. Recognizer P systems with active membranes (using division rules and, eventually, polarizations associated to membranes) have thus been successfully used to efficiently solve NP-complete problems. The first solutions were given in the so called semi-uniform setting [13, 23, 7, 9], which means that we assume the existence of a deterministic Turing machine that, for every instance of the problem, produces in polynomial time a description of the P system that solves such an instance. The solution is computed in a confluent manner, meaning that the instance given in input is positive if and only if every computation of the P system Recognizer P Systems with Strong Division and Dissolution 263 associated with it is an accepting computation. Another way to solve NP-complete problems by means of P systems is by considering the uniform setting, in which all the instances of the problem are given in input — encoded in an appropriate way — to the same P system and then solved by it. Sometimes, a uniform solution to a decision problem Qis provided by defining a family {ΠQ(n)}n∈Nof P systems such that for every n∈Nthe system ΠQ(n) reads in input an encoding of any possible instance of size n, and solves it. P systems with active membranes have thus been successfully used to design uniform polynomial-time solutions to some wellknown NP-complete problems, such as sat [20], Subset Sum [17], Knapsack [18], Partition [6] and the Common Algorithmic Problem [21]. All the papers mentioned above deal with P systems with three polarizations that use only division rules for elementary membranes (in [22] also division for non–elementary membranes is permitted, and in this way a semi–uniform solution to the PSPACE-complete problem qsat is provided), and working in the maximal parallel way. As shown in [1], the number of polarizations can be decreased to two without loss of efficiency. Since by using all these features (membrane division, dissolution and polarizations) we can solve NP-complete problems, we have a model of computation which is considered too powerful from the point of view of traditional complexity theory. Hence a research direction of a clear interest is to selectively remove one or more of these features and see whether the computation power changes, that is, investigating for what combinations of features we are still able to obtain polynomial time solutions to computationally hard problems and what features, once removed, only allow to obtain polynomial time solutions to tractable problems, in the classical sense. In this direction, in [15] a conjecture was formulated by Gh. P˘aun about the computational power of polarizationless P systems with active membranes and working in the maximally parallel mode, stating that such systems can only solve decision problems that are in P(by using only elementary division), and some partial answers were given in [8]. Also, in [4] the computational power of recognizer P systems with active membranes but without electrical charges and dissolution rules was investigated, establishing that they characterize the complexity class P. In this paper we continue this research line, showing that polarizationless P systems with active membranes that use strong division for non–elementary membranes and dissolution rules, working in the maximal parallel way, are able to solve in polynomial time the NP-complete problem 3-sat. This result provides further partial answers to P˘aun’s conjecture, establishing that neither evolution nor communication rules, and no electrical charges are needed to solve NP-complete problems, provided that we can use strong division rules for non–elementary membranes (as well as dissolution rules, otherwise we would fall in the case considered in [4]). The paper is organized as follows. In Sections 2 and 3 we recall the definition of polarizationless recognizer P systems with active membranes, thus establishing our model of computation, and we recall the definition of the NP-complete decision problem 3-sat. In Section 4 we show how the systems we are considering are able 264 C. Zandron et al. to solve the 3-sat problem. Finally, Section 5 contains the conclusions and some directions for further research. 2 Polarizationless recognizer P systems with active membranes Usually, P systems with active membranes are defined in the literature with three electrical charges (also called polarizations) associated with membranes (even thought two charges suffice, as proved in [1]) to control the application of the rules, which can be of the following types: evolution rules, by which single objects evolve to a multiset of objects, communication rules, by which an object is introduced in or expelled from a membrane, and possibly changed to another object while performing this operation, dissolution rules, by which a membrane is dissolved under the influence of an object, that can also be modified during this operation, and membrane division rules (both for elementary and non–elementary membranes, or only for elementary membranes). However, in this paper we will consider polarizationless P systems with active membranes, that is, P systems in which no electrical charge is associated with any membrane. Formally, a P system with polarizationless active membranes of the initial degree n≥1 is a tuple of the form Π= (Γ, H, µ, M1, . . . , Mn, R, h0), where: 1. Γis the alphabet of objects; 2. His a finite set of labels for membranes; 3. µis a membrane structure, consisting of nmembranes being labelled with elements of H; 4. M1, . . . , Mnare strings over Γ, describing the multisets of objects placed in the ninitial regions of µ; 5. Ris a finite set of developmental rules, of the following forms: (a) [ a→v]h, for h∈H,a∈Γ,v∈Γ∗(object evolution rules); (b) a[ ]h→[b]h, for h∈H,a, b ∈Γ(in communication rules); (c) [ a]h→b[ ]h, for h∈H,a, b ∈Γ(out communication rules); (d) [ a]h→b, for h∈H,a, b ∈Γ(dissolution rules); (e) [ a]h→[b]h[c]h, for h∈H,a, b, c ∈Γ(weak division rules for elementary or non–elementary membranes); (f) h0∈Hor h0=env indicates the output region (in the latter case, usually h0does not appear in the description of the system). We can also consider rules of the form [ [ ]h1[ ]h2]h3→[ [ ]h1]h3[ [ ]h2]h3, where h1,h2,h3are labels from H: if the membrane with label h3contains other membranes than those with labels h1, h2, these membranes and their contents are duplicated and placed in both new copies of the membrane h3; all membranes and objects placed inside membranes h1, h2, as well as the objects from membrane h3placed outside membranes h1and h2, are reproduced in the new copies of membrane h3. These rules are called strong division rules for non–elementary membranes. Recognizer P Systems with Strong Division and Dissolution 265 As usual, a computation starts in the initial configuration, which is given by the membrane structure µand the strings (multisets) M1, . . . , Mnof objects initially present in the nregions of µ. Using the maximally parallel manner, at each computation step (a global clock is assumed) in each region of the system we apply the rules in such a way that no further rule can be applied to the remaining objects or membranes. In each step, each object and each membrane can be involved in only one rule. The application of a maximal set of rules during a computation step produces a new configuration of the system. A computation is a sequence C0, C1, . . . of configurations such that C0is the initial configuration described above, and for all i≥1 the configuration Ciis obtained from Ci−1by applying a maximal set of rules as described above. Note that a computation may be finite or infinite; in the former case we require that the last element of the sequence is an halting configuration, that is, a configuration in which no rule can be applied anywhere in the system. A halting computation provides a result encoded by the objects present in region h0at the end of the computation; this is a region of the system if h0∈H(and in this case, for a computation to be successful, exactly one membrane with label h0should be present in the halting configuration), or it is the environment if h0=env. An infinite computation produces no result. Arecognizer P system with active membranes is obtained from the definition given above by assuming that the system halts on every computation and produces one of two possible outputs, that are usually denoted by yes and no. A further requirement is that the system is confluent, that is, for any given input configuration, all the computations that can start with such a configuration end by producing the same output. In this way, we can say that a recognizer P system with active membranes recognizes the language which is composed by the strings that encode the initial configurations that produce yes as a result. By considering the trivial bijection existing between these languages and decision problems, we can also say that a recognizer P system solves the decision problem whose positive instances are associated with initial configurations of the system that produce the output yes in h0. We denote by AM0the class of polarizationless recognizer P systems with active membranes, and we denote by AM0(α, β, γ, δ), where α∈ {−d, +d},β∈ {−ne, +new, +nes},γ∈ {−ev, +ev}, and δ∈ {−comm, +comm}the class of all recognizer P systems with polarizationless active membranes such that: (a) if α= +d(resp., α=−d) then dissolution rules are permitted (resp., forbidden); (b) if β∈ {+new, +nes}(resp., β=−ne) then division rules for elementary and non– elementary membranes, weak or strong (resp., only division rules for elementary membranes) are permitted; (c) if γ= +ev (resp., γ=−ev) then evolution rules are permitted (resp., forbidden); (d) if δ= +comm (resp., δ=−comm) then communication rules are permitted (resp., forbidden). The class of all decision problems which can be solved in uniform (resp., semi– uniform) way, and in polynomial time by a family Rof recognizer membrane systems is denoted by PMCR(resp., PMC∗ R). The following inclusions directly follow from these definitions. 266 C. Zandron et al. Proposition 1. For all α∈ {−d, +d},β∈ {−ne, +new, +nes},γ∈ {−ev,+ev}, δ∈ {−comm, +comm}and ε∈ {∗, λ}: 1. PMCAM0(α,β,γ,δ)⊆PMC∗ AM0(α,β,γ,δ) 2. PMCε AM0(−d,β,γ,δ)⊆PMCε AM0(+d,β,γ,δ) 3. PMCε AM0(α,−ne,γ,δ)⊆PMCε AM0(α,+new,γ,δ) 4. PMCε AM0(α,−ne,γ,δ)⊆PMCε AM0(α,+nes,γ,δ) 5. PMCε AM0(α,β,−ev,δ)⊆PMCε AM0(α,β,+ev,δ) 6. PMCε AM0(α,β,γ,−comm)⊆PMCε AM0(α,β,γ,+comm) where ε=∗(resp., ε=λ, the empty string) means that the complexity classes are associated with semi–uniform (resp., uniform) solutions. Also, using this notation, P˘aun’s conjecture (problem Fin [15]) can be restated as follows: P=PMCAM0(+d,−ne,+ev,+comm)=PMC∗ AM0(+d,−ne,+ev,+comm) As stated in the Introduction, results in [4] and [8] proved the following theorem, considering a reachability problem (is the state in which the symbol yes is expelled to the environment reachable?) defined on the so called dependency graph. We refer the reader to [4] and [8] for further details on the proofs. Theorem 1. For all β∈ {−ne, +new, +nes}, P=PMCAM0(−d,β,+ev,+comm)=PMC∗ AM0(−d,β,+ev,+comm) This result holds for systems working in the maximal parallel manner; in [8] also systems working with minimal parallelism were considered, but in this paper we will not address them. 3 The 3-sat problem Let us now consider the NP-complete decision problem 3-sat [3, p. 46]. The instances of 3-sat depend upon two parameters: the number nof variables, and the number mof 3-clauses. We recall that a clause is a disjunction of literals, occurrences of xior ¬xi, built on a given set X={x1, x2, . . . , xn}of boolean variables. A 3-clause is a clause that contains exactly three literals. In what follows we will require that no repetitions of the same literal may occur in any clause. Without loss of generality we can also avoid the clauses in which both the literals xiand ¬xi, for any 1 ≤i≤n, occur. An assignment of the variables x1, x2, . . . , xn is a mapping a:X→ {0,1}that associates to each variable a truth value. The number of all possible assignments to the variables of Xis 2n. We say that an assignment satisfies the clause Cif, assigned the truth values to all the variables which occur in C, the evaluation of C(considered as a boolean formula) gives 1 (true) as a result. We can now formally state the 3-sat problem as follows. Recognizer P Systems with Strong Division and Dissolution 267 Problem 1. Name: 3-sat. •Instance: a set C={C1, C2, . . . , Cm}of 3-clauses, built on a finite set {x1, x2, . . . , xn}of boolean variables. •Question: is there an assignment of the variables x1, x2, . . . , xnthat satisfies all the clauses in C? In what follows we will sometimes equivalently say that an instance of 3-sat is a propositional formula γn,m =C1∧C2∧ · · · ∧ Cm, expressed in the conjunctive normal form as a conjunction of mclauses, where each clause is a disjunction of three literals built using the boolean variables x1, x2, . . . , xn. With a little abuse of notation, from now on we will denote by 3-sat(n, m) the set of instances of 3-sat which have nvariables and mclauses. The reason for which we are here interested into 3-sat (rather that with the more generic problem sat, see [3, p. 39], where we put no upper bound on the number of literals that may appear in each clause) is that the number of possible 3clauses which can be built using nboolean variables is 2n·(2n−2)·(2n−4) ∈Θ(n3), a polynomial quantity with respect to n. This quantity is obtained by looking at a 3-clause as a triple, and observing that each component of the triple may contain one of the 2npossible literals, with the constraints that we do not allow neither the repetition of literals in the clauses, nor the use of the same variable two or three times in a clause. On the other hand, an instance of sat may have a number of clauses which is exponential in n, since for every i∈ {1,2, . . . , n}either variable xior its negation (or none of them) can appear in a clause, yielding to 3npossible combinations. 4 Solving 3-sat with strong division and dissolution rules In this section we propose a semi–uniform family {Π3SAT (γn,m)}γn,m∈3SAT (n,m) of polarizationless recognizer P systems with active membranes that solves the NP-complete decision problem 3-sat by using only membrane dissolution rules and a form of strong division rules for non–elementary membranes. Precisely, for every instance γn,m of 3-sat(n, m) we show how to build the system Π3SAT (γn,m) that solves such an instance. Our result can be summarized by the statement of the following theorem. Theorem 2. 3-sat ∈PMC∗ AM0(+d,+nes,−ev,−comm). Proof. Let γn,m =C1∧C2∧. . .∧Cmbe an instance of 3-sat(n, m), built using the boolean variables x1, x2, . . . , xn, and let Π3SAT (γn,m) be the recognizer P system associated (in the semi–uniform framework) to γn,m, whose initial configuration is illustrated in Figure 1. The system is composed by mouter membranes (not counting the skin membrane) which are associated with the clauses of γn,m. Precisely, the membrane immediately contained in the skin is associated with clause Cmand contains membrane Cm−1, which is associated with the namesake clause; 268 C. Zandron et al. Fig. 1. Initial configuration of the system Π3SAT (γn,m) that solves the instance γn,m of 3-sat(n, m) on its turn, membrane Cm−1contains a membrane labelled with Cm−2, and so on, until we reach membrane C1that contains a membrane labelled with A, that will be used to generate all the possible assignments to x1, x2, . . . , xn. Membrane Acontains the object x1(that represents the namesake variable) as well as nhierarchies of nested membranes. As depicted in Figure 2, the notation xik dithat we Fig. 2. The hierarchies of nested membranes used in the system depicted in Figure 1 to perform the correct sequence of membrane divisions have adopted in Figure 1 indicates that symbol xiis surrounded by kmembranes, nested one into the other, all labelled by di. In this way, we can operate on membrane Athrough a rule which is activated by x1and, in the meanwhile, dissolve one membrane in each of the subsystems contained in A. After m+ 1 steps x2 emerges and activates another rule of A, and so on, until symbol semerges and starts another phase of computation. Recognizer P Systems with Strong Division and Dissolution 269 The computation of the system is composed by two phases: the generation stage and the verification stage. During the generation stage, 2ncopies of the subsystem contained into the skin of the initial configuration depicted in Figure 1 are produced, where in each copy membrane Acontains an encoding of one of the possible assignments to x1, x2, . . . , xn. Such a phase is performed by the following rules: 1. [ [ ]A[ ]A]C1→[ [ ]A]C1[ [ ]A]C1 2. [ [ ]Ci−1[ ]Ci−1]Ci→[ [ ]Ci−1]Ci[ [ ]Ci−1]Cifor all i= 2,3, . . . , m 3. [ xj]A→[tj]A[fj]Afor all j= 1,2, . . . , n 4. [ xj]dj→xjfor all j= 1,2, . . . , n 5. [ s]ds→s 6. [ s]A→yes 7. [ tj]Ci→tjif xj∈Ci, [ fj]Ci→fjif ¬xj∈Ci, where 1 ≤i≤m Rules 1 and 2 are strong division rules for non–elementary membranes: whenever a membrane Cicontains two membranes at their immediately inner level, it divides and each of the resulting copies contains one of the previous inner membranes. Rule 3 is used to generate the assignments: when the symbol xj, for j∈ {1,2, . . . , n}, occurs in membrane Athen Adivides; in one of the resulting copies the symbol xj is rewritten to tj, indicating the fact that we are assigning the value true to the boolean variable xj. Similarly, in the other copy of Athe symbol xjis rewritten to fj, indicating that the boolean value false is assigned to xj. In order to control the order of application of division rules during the generation phase, only one symbol xjoccurs in membrane Aevery m+ 1 computation steps. In this way we first divide membrane A, assigning the two boolean values true and false to xj as described above; then, rule 1 can be applied, thus duplicating membrane C1. In the subsequent m−1 computation steps, membranes C2, C3, . . . , Cmare duplicated exactly in this order thanks to rules 2. Figure 3 depicts the first steps of this process for an instance containing n= 2 variables and m= 2 clauses (note that this example is conceived only for illustrative purposes, since at least three boolean variables are needed to build valid 3-clauses). The rules are applied in the maximal parallel manner. In particular, at every computation step one membrane labelled with dj, for each j∈ {1,2, . . . , n}such that membrane djstill occurs in the system, is dissolved. In this way, a symbol xj emerges in membrane Ajust after the assignment to xj−1and all the subsequent duplications of membranes C1, C2, . . . , Cmhave been performed. By using the same mechanism, symbol semerges in membrane Aafter n(m+ 1) steps, that is, after all the assignments to x1, x2, . . . , xnand all the duplications of membranes C1, C2, . . . , Cmhave been performed. In practice, the construct composed by n(m+ 1) nested membranes, all labelled with ds, together with the symbol sinto the innermost membrane and the dissolution rule [ s]ds→s, implement a counter whose initial value is nm and which is decremented each time the dissolution rule is applied. When the symbol sappears in Athen n(m+ 1) computation steps have been performed, that is, the generation stage has ended and the verification stage can