Solving Problems Through a Single Membrane System

Solving Problems Through a Single Membrane System David Orellana-Mart´ın, Luis Valencia-Cabrera, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {dorellana,lvalencia,ariscosn,marper}@us.es Summary. The tape of a deterministic Turing machine contains an unbounded number of cells. Thanks to that, a single machine can solve decision problems with an infinite number of instances. Nevertheless, in the framework of membrane computing, traditionally a “solution” to an abstract decision problem consists of a family of membrane systems (where each system of the family is associated with a finite set of instances of the problem to be solved). An interesting question is to analyze the possibility to find a single membrane system able to deal with the infinitely many instances of a decision problem. In this context, it is fundamental to define precisely how the instances of the problem are introduced into the system. In this paper, two different methods are considered. The first one relies on a pre-computing process, where a polynomial-time computable function will be in charge of producing a multiset of objects associated with the instance to be solved. On the other hand, the second one assumes that the input alphabet of the system is equal to the alphabet of instances, and therefore instances are directly introduced in the initial configuration of the system. Polynomial complexity classes associated with these two approaches are introduced and some complexity aspects are studied. 1 Introduction In the 17th Brainstorming Week on Membrane Computing, an apparently innocent problem was presented by the authors: the ONLY-ONE-OBJECT problem. The goal is to build a system able to distinguish whether in a given region, at a given moment, there is only one copy of an object, or if the multiplicity of the object is strictly greater than one. Besides, the notion of efficient solvability by means of a single recognizer polarizationless P system with active membranes, without dissolution rules and using division for elementary and non-elementary membranes, was proposed. Following a reasoning based on the dependency graph technique, a 440 D. Orellana-Mart´ın et al. negative answer to the previous question was concluded (i.e. the problem is not solvable in the proposed framework). In some sense, the previous question links up with others that were proposed by P. Sos´ık [17], which raise the possibility of being able to solve P-complete problems or NP-complete problems by means of a single membrane system. Specifically, two “open problems” were “formulated” in [17], expressed in an informal way as follows: •Open Problem 1. Is there any known standard model of P system capable of solving a P-complete problem in polynomial time without the use of families, i.e., all instances are solved by the same P systems? •Open Problem 2. How to design a natural (not much “extraordinary”) model of P system capable of solving an NP-complete problem in polynomial time without the use of families? Of course, these questions should be expressed in a formal way and their answers will depend on the definitions given about what solving a decision problem through a single membrane system means. For instance, two possible definitions could be considered according to the way of entering the input inside the membrane system: (a) by using precomputed resources (that is, waiting for a polynomial time prior to the initial step of the computation, to calculate which is the input multiset that has to be provided to the system); or (b) by directly introducing the input multiset without any preprocessing, that is, free of external resources. For a comprehensive introduction to membrane systems, we refer the reader to [12, 15]. 2 The Complexity Class PMC1p R First, let us define a solution to a decision problem through a single membrane system allowing the possibility to use (external) precomputed resources for providing the input multiset to the system. In other words, we assume that there is an available device able to execute the function that computes the input multiset, and this process should be performed before the computation of the membrane system starts. Definition 1. Let Rbe a class of recognizer membrane system. Let X= (IX, θX) be a decision problem. We say that problem Xis solvable in polynomial time by a single membrane system Πfrom Rwith precomputed resources, denoted by X∈ PMC1p R, if the following hold: •There exists a polynomial encoding cod from Xto Πproviding a “reasonable encoding scheme” which maps problem instances into the multisets describing them [3]; that is, there exists a polynomial time computable function, cod, whose domain is IXsuch that for every instance u∈IX,cod(u)is a multiset over the input alphabet of Π. Solving Problems Through a Single Membrane System 441 •The system Πis polynomially bounded with regard to (X, cod); that is, there exists a polynomial p(r)such that for each instance u∈IX, every computation of the system Πwith input multiset cod(u)performs at most p(|u|)steps. •The system Πis sound with regard to (X, cod); that is, for each instance u∈ IX, if there exists an accepting computation of the system Πwith input multiset cod(u)then θX(u)=1. •The system Πis complete with regard to (X, cod); that is, for each instance u∈IXsuch that θX(u) = 1, every computation of the system Πwith input multiset cod(u)is an accepting computation. In this definition, the input multiset that is allocated into the initial configuration of the system is precomputed by means of a polynomial-time computable function. Proposition 1. If Ris a class of recognizer membrane systems, then P⊆PMC1p R⊆PMCR Proof. In order to show that P⊆PMC1p R, let X= (IX, θX) be a decision problem in class P. Let us consider the deterministic recognizer (cell-like) membrane system Π={Γ, Σ, µ, M1,R, iin}of degree 1 defined as follows: •Γ=Σ={yes,no}. •µ= [ ]1. • M1=∅ • R ={[yes ]1→yes [ ]1; [ no ]1→no [ ]1} •iin = 1. Let us consider cod as the map whose domain is IXdefined as follows: for every u∈IX,cod(u) = {yes}if θX(u) = 1, and cod(u) = {no}, otherwise. Since X∈P, cod is a polynomial-time function. Then, we have: •The system Πis polynomially bounded with regard to (X, cod): for every instance u∈IX, the computation of Πwith input multiset cod(u) performs 1 transition step. •For every instance u∈IX, the computation of the system Πwith input multiset cod(u) is an accepting computation if and only if θX(u) = 1. This definition can be easily adjusted for any class of recognizer membrane systems R, in such a way that we have X∈PMC1p R. Then, we conclude that P⊆PMC1p R. In order to show that PMC1p R⊆PMCR, let X= (IX, θX) be a decision problem such that X∈PMC1p. Let Π0a membrane system from Rsolving X according to Definition 1, being cod0apolynomial encoding from Xto Πassociated with that solution. Let us consider the family Π={Π(t)|t∈N}defined as follows Π(t) = Π0, for each t∈N. Let us consider the polynomial encoding (cod, s) from the problem Xto the family Πdefined as follows: cod =cod0and s(u) = 0, for each u∈IX. Then it is easy to check that the family Πis polynomially uniform 442 D. Orellana-Mart´ın et al. by Turing machines, polynomially bounded with regard to (X, cod, s), and sound and complete with regard to (X, cod, s). Thus, X∈PMCR.  3 The Complexity Class PMC1f R The second definition refers to the case in which the input multiset is directly introduced inside the system as it is (“free” of external dependencies or resources), and thus the input alphabet should be chosen so that the system is able to “read” the instances of the problem to be solved. Definition 2. Let Rbe a class of recognizer membrane systems. Let X= (IX, θX) be a decision problem such that IXis a language over a finite alphabet ΣX. We say that problem Xis solvable in polynomial time by a single membrane system Π from Rfree of external resources, denoted by X∈PMC1f R, if the following hold: •The input alphabet of Πis ΣX. •The system Πis polynomially bounded with regard to X; that is, there exists a polynomial p(r)such that for each instance u∈IX, every computation of the system Πwith input multiset uperforms at most p(|u|)steps. •The system Πis sound with regard to X; that is, for each instance u∈IX, if there exists an accepting computation of the system Πwith input multiset u then θX(u)=1. •The system Πis complete with regard to X; that is, for each instance u∈IX such that θX(u)=1, every computation of the system Πwith input multiset u is an accepting computation. Proposition 2. Let Rbe a class of recognizer membrane systems. Then we have PMC1f R⊆PMC1p R. Proof. Let us assume that X∈PMC1f R. Let Π0a membrane system from R whose input alphabet is ΣX(the working alphabet of the problem X) such that it is polynomially bounded, sound and complete with regard to X. Let us consider the polynomial encoding cod from Xto Π0defined as follows: cod(u) = u, for every instance u∈IX. Then, Π0is polynomially bounded, sound and complete with regard to (X, cod). Thus, X∈PMC1p R. 4 Decision Problems with a Finite Number of Instances In this section, we work with decision problems whose set of instances is a finite set. Proposition 3. Let T(so)the class of all recognizer transition P systems which make use of send-out communication rules only. Then, if X= (IX, θX)is a decision problem whose set of instances is a finite set, then X∈PMC1f T(so). Solving Problems Through a Single Membrane System 443 Proof. Let X= (IX, θX) be a decision problem whose set of instances IXis a finite language over the alphabet ΣX. Let us consider the recognizer transition P system Π= (Γ, Σ, µ, M1,R1, iin), defined as follows: •The working alphabet is Γ=ΣX∪ {yes,no}and the input alphabet Σis ΣX. •The membrane structure is µ= [ ]1and the initial multiset is M1=∅. •The set R1of rules is {[u]1→yes [ ]1|θX(u)=1}∪{[u]1→no [ ]1|θX(u)=0} •The input membrane is labelled by 1. Obviously, membrane system Πbelongs to the class T(so) and it solves problem X, according to Definition 2. 4.1 The logic gate problems Definition 3. A Boolean function of arity n≥1is a total function ffrom {0,1}n to {0,1}. Usually, in this context, Boolean values 0, 1 can be associated with false and true. Specifically, value 0 is associated with the logical value false (denoted by 0∗) and value 1 is associated with the logical value true (denoted by 1∗). The logical connective ¬can be considered as a unary Boolean function and the logical connectives ∧,∨can be considered as binary Boolean functions. Any Boolean expression ϕwhose set of variables is V ar(ϕ) = {x1, . . . , xn}, can be viewed as the n-ary Boolean function fverifying the following: for any tuple (t1, . . . , tn)∈ {0,1}nwe have f(t1, . . . , tn) = 1 if and only if σ(ϕ) = true, where σis the truth assignment (t∗ 1, . . . , t∗ n). Any Boolean function of arity n≥1 has associated a decision problem Xf= (IXf, θXf), in a natural way, as follows: IXf={0,1}nand θXf(x1, . . . , xn) = f(x1, . . . , xn), for each (x1, . . . , xn)∈ {0,1}n. As an interesting case of Boolean functions, we consider the following decision problems associated with logic gates. •NOT-GATE= ({0,1}, θ), where θ(0) = 1 and θ(1) = 0. •OR-GATE= ({0,1} × {0,1}, θ), where θ(u) = 0, if u= (0,0), and θ(u) = 1, otherwise. •AND-GATE= ({0,1} × {0,1}, θ), where θ(u) = 1, if u= (1,1), and θ(u) = 0, otherwise. Proposition 4. Let T(nc, so)the class of all recognizer transition P systems which makes only use of non-cooperative send-out communication rules. Then, problems NOT-GATE,OR-GATE,AND-GATE belong to PMC1f T(nc,so). Proof. Let us consider the P system Π= (Γ, Σ, µ, M1,R1, iin) defined as follows: 444 D. Orellana-Mart´ın et al. •The working alphabet is Γ=Σ∪ {yes,no}and the input alphabet Σ={0,1} . •The membrane structure is µ= [ ]1and the initial multiset is M1=∅. •The set R1of rules is {[ 0 ]1→yes ; [ 1 ]1→no [ ]1}. •The input membrane is labelled by 1. Obviously, system Πfrom class T(nc, so) solves the NOT-GATE problem, according to Definition 2. With respect to the OR-GATE problem, let us consider the P system Π= (Γ, Σ, µ, M1,R1, iin) defined as follows: •The working alphabet Γ=Σ∪ {yes,no}and the input alphabet Σ={0,1} × {0,1}. •The membrane structure is µ= [ ]1and the initial multiset is M1=∅. •The set R1of rules is {[ (u, v) ]1→yes [ ]1|(u, v)∈ {0,1}×{0,1}, u +v≥1} ∪ {[ (0,0) ]1→no [ ]1}. •The input membrane is labelled by 1. Obviously, system Πfrom class T(nc, so) solves the OR-GATE problem, according Definition 2. In a similar way, it can be shown that the AND-GATE problem belongs to PMC1f T(nc,so). It is worth pointing out that in this kind of solution by means of a single membrane system using non-cooperative rules, the representation of the instances is specially relevant. For instance, in the case of the OR-GATE problem and the AND-GATE problem, the cooperation in the rules of the system can be avoided because the set of instances is described by symbols of the language {0,1}×{0,1}. 5 The NONE-OBJECT Problem In this section, we consider the NONE-OBJECT problem which informally corresponds to the task of determining whether there is any input object or not in the system. Formally, let X= (IX, θX) be the decision problem defined as follows: IX={∅} ∪ {an|n∈N, n ≥1}, θX(∅)=1,and θX(an) = 0 for each n≥1 That is, the problem Xdistinguishes two types of situations: absence of objects on one hand, and at least one copy of object a, on the other hand. Theorem 1. Let T(nc, ev, so, dis, pr)the class of all non-cooperative recognizer P systems which makes use of minimal production in object evolution rules (that is, only one object in the right-hand side of the rule), send-out communication rules, dissolution rules and priorities. Then, NONE-OBJECT∈PMC1f T(nc,ev,so,dis,pr). Proof. Let us consider the system Πfrom T(nc, ev, so, dis, pr) defined as follows: •The working alphabet is Γ={a, b, c}and the input alphabet is Σ={a}. Solving Problems Through a Single Membrane System 445 •The membrane structure µis µ= [ [ ]2]1and the initial multisets are M1=∅ and M2={c}. •The set Rof rules of Πis the following: {[a→b]2; [ b]2→no; [ c]2→yes; [ yes]1→yes [ ]1; [ no]1→no [ ]1} •The set of priorities Pamong rules of Πis the following: ([ a→b]2,[c]2→yes); ([ b]2→no,[c]2→yes) •The input membrane is labelled by 2. Then, the following hold: •For each natural number n≥1, the system Πwith input multiset {an}is deterministic, the computation of Π+{an}performs three transition steps and it is a rejecting computation. •The system Πwith input multiset ∅is deterministic, the computation of Π+∅ performs two transition steps and it is an accepting computation. Thus, NONE-OBJECT∈PMC1f T(nc,ev,so,dis,pr). 6 The ONLY-ONE-OBJECT Problem In this section, the problem of telling apart “one” from “more-than-one” object is considered. Formally, let X= (IX, θX) be the decision problem defined as follows: IX={an|n∈N, n ≥1}and θX(an) = 1 if and only if n= 1 That is, the problem Xdistinguishes the case when there is only one copy of object afrom the rest of possible cases with several copies of that object. We denote that problem as the ONLY-ONE-OBJECT problem. Obviously, the ONLY-ONE-OBJECT problem belongs to class Psince it is easy to design a deterministic Turing machine solving that problem which takes two computation steps. Thus, ONLY-ONE-OBJECT∈P. Bearing in mind that for every class Rof recognizer membrane systems, we have we P⊆PMC1p R, we deduce that ONLY-ONE-OBJECT∈PMC1p R. It is easy to prove that ONLY-ONE-OBJECT∈PMC1f T(nc,ev,so,dis,pr), but the following result shows that this problem cannot be solved by a membrane system from AM0(−d, +ne) without using precomputed resources, being AM0(−d, +ne) the class of polarizationless P systems without dissolution rules and with division rules for elementary and non-elementary membranes. Theorem 2. There does not exist a recognizer membrane system Π0∈ AM0(−d, +ne)solving the ONLY-ONE-OBJECT problem in a polynomial time by a single membrane system and free of resources. That is, ONLY-ONE-OBJECT/∈ PMC1f AM0(−d,+ne). 446 D. Orellana-Mart´ın et al. Proof. (Reasoning by reductio ad absurdum) Let us assume that there exists a recognizer membrane system Π0from AM0(−d, +ne) verifying the following: (a) The input alphabet of Π0is the singleton {a}. (b) Every computation of Π0with input multiset {a}is an accepting computation. (c) Every computation of Π0with input multiset {an}, for each n > 1, is a rejecting computation. Let us denote by GΠ0+{a}(respectively, GΠ0+{an}, for each n > 1) the dependency graph1associated with the system Π0+{a}(resp. Π0+{an}). Then, we have: •For each n > 1, GΠ0+{a}=GΠ0+{an}. Indeed, in both graphs there is only one edge starting from s, specifically, the edge {s, (a, iin)}, and the rest of edges are given by the rules of Π0, due to Π0∈ AM0(−d, +ne). •A computation of Π0+{a}is an accepting computation if and only if there exists a path in GΠ0+{a}from sto (yes, env). •For each n > 1, a computation of Π0+{an}is an accepting computation if and only if there exists a path in GΠ0+{an}from sto (yes, env). Thus, bearing in mind that GΠ0+{a}=GΠ0+{an}we deduce that every computation of Π0+{a}is an accepting computation if and only if every computation of Π0+{an}, for each n > 1, is an accepting computation. Hence, conditions (b) and (c) are contradictory.  Corollary 1. PMC1f AM0(−d,+ne)(P⊆PMC1p AM0(−d,+ne). 7 A Version of the PARITY Problem In this section, a version of the PARITY problem is considered. Specifically, let PARITY = (IPARITY, θPARITY) be the decision problem defined as follows: IPARITY ={an|n∈N, n ≥1}and θPARITY(an) = 1 if and only if nis even That is, the PARITY problem distinguishes an even number of copies of object a from an odd number of copies of that object. Obviously, this version of the PARITY problem belongs to class Psince it is easy to design a deterministic Turing machine solving that problem. Theorem 3. Let T(mcmp, so, dis, pr)the class of all recognizer P systems which make use of minimal cooperation and minimal production in object evolution rules, send-out communication rules, dissolution rules and priorities. Then, PARITY∈ PMC1f T(mcmp,so,dis,pr). 1We will not recall the formal definition here (see [2, 18] for details). The dependency graph can be intuitively seen as a map of “reactants-product” relationship between objects: the nodes are pairs (object, region) and for every rule of the system there will be an arc connecting each object on the left-hand-side to each object on the right-hand side. Solving Problems Through a Single Membrane System 447 Proof. Let us consider the system Πfrom T(mcmp, so, dis, pr) defined as follows: (a) The working alphabet is Γ={a, b}and the input alphabet is Σ={a}. (b) The membrane structure is µ= [ [ ]2]1, and the initial multisets are M1=∅ and M2=∅. (d) The set Rof rules of Πis the following: {[a2→b]2; [ b2→b]2; [ a]2→no; [ b]2→yes}∪ {[no]1→no [ ]1; [ yes]1→yes [ ]1} (e) The set of priorities Pamong rules of Πis the following: ([ a2→b]2,[a]2→no); ([ b2→b]2,[a]2→no); ([ a2→b]2,[b]2→yes); ([ b2→b]2,[b]2→yes); ([ a]2→no,[b]2→yes) (f) The input membrane is labelled by 2. Then, for each natural number n≥1, the following hold: •The system Πwith input multiset {an}is deterministic. •The computation of Π+{an}performs 2 + blog2(n)ctransition steps. •The natural number nis odd if and only if the configuration Cblog2(n)ccontains a copy of object a. •The natural number nis even if and only if the computation of Π+{an}is an accepting computation. Thus, PARITY∈PMC1f T(mcmp,so,dis,pr). 8 Conclusions In this work, the ability of solving problems by single “stand-alone” membrane systems instead of families of membrane systems is studied. While using precomputed resources, it is easy to see that problems from Pcan be solved by a single membrane system using only send-out rules. A question arises from here: What if we cannot access to a precomputed encoding and we have the raw instance as input? In this paper, the power of single membrane systems free of precomputed resources is also studied, giving, on the one hand, solutions to decision problems by means of a single membrane system solving them, and on the other hand demonstrating the inability of systems from AM0(−d, +ne) to solve the ONLY-ONE-OBJECT problem by using the dependency graph technique in a novel way. While talking about recognizer membrane systems, we suppose that they can, at least, send an object to the environment to return the answer. Even with this minimal definition, the lower bound for PMC1p Rhas been demonstrated to be