P systems with input in binary form

P SYSTEMS WITH INPUT IN BINARY FORM ALBERTO LEPORATI∗ CLAUDIO ZANDRON† Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano – Bicocca Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy and MIGUEL A. GUTI´ ERREZ-NARANJO‡ Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Sevilla University Avda Reina Mercedes s/n, 41012 Sevilla, Spain Received (received date) Revised (revised date) Communicated by Editor’s name ABSTRACT Current P systems which solve NP–complete numerical problems represent instances in unary notation. In classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances generally corresponds to simplify the problem. In this paper we show that this does not occur when working with P systems. Namely, we propose a simple method to encode binary numbers using multisets, and a family of P systems which transforms such multisets into the usual unary notation.a Keywords: Membrane Computing; P systems; Binary data; Partition 1. Introduction P systems (also called membrane systems) were introduced in [?] as a new class of distributed and parallel computing devices, 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. The rules are applied in a nondeterministic and maximally parallel way: all the objects that may evolve are ∗lep[email protected]t. †[email protected]. ‡[email protected] 1 forced to evolve. A computation starts from an initial configuration of the system and terminates when no evolution rule can be applied. The result of a computation is the multiset of objects contained into an output membrane or emitted to the environment from the skin of the system. In what follows we assume the reader is already familiar with the basic notions and the terminology underlying P systemsb. Many P systems which solve NP–complete decision problems have appeared in the literature during the last few years. Both in the field of numerical problems, that is, problems whose instances consist of sets or sequences of integer numbers (see for example Subset Sum [?], Knapsack [?], Bin Packing [?] or Partition [?] problems) or non-numerical problems as SAT [?,?] or QSAT [?]. It is well known [?,?] that the difficulty of such numerical problems is tied to the magnitude of the numbers which appear into the instance. For example, let us consider the Partition problem, which can be stated as follows: Problem 1.1 Name:Partition. •Instance: a set A={a1, a2,...,an}of positive integer numbers •Question: is there a subset A′⊆Asuch that P a′∈A′ a′=P a∈A\A′ a? The following algorithm solves the problem using the well known Dynamic Programming technique [?]. In particular, the algorithm returns 1 on positive instances, and 0 on negative instances. Partition({a1, a2,...,an}) s←Pn i=1 ai if smod 2 = 1 then return 0 for j←1to s/2 do M[1, j]←0 M[1,0] ←M[1, a1]←1 for i←2to n do for j←0to s/2 do M[i, j]←M[i−1, j] if j≥aiand M[i−1, j −ai]> M[i, j] then M[i, j]←M[i−1, j −ai] return M[n, s/2] First of all, the algorithm computes the sum sof all elements in the instance. If s is odd then the instance is certainly negative, and thus the algorithm returns 0. If sis even then the algorithm checks for the existence of a subset A′⊆Asuch that Pa′∈A′a′=s 2. In order to look for A′, the algorithm uses a n×(s 2+ 1) matrix Mwhose entries are from {0,1}. It fills the matrix by rows, starting from the first row. Each row is filled from left to right. The entry M[i, j] is filled with 1 if and bA layman-oriented introduction can be found in [?]; a formal description in [?] and the latest information about P systems can be found on [?]. 2 only if there exists a subset of {a1, a2,...,ai}whose elements sum up to j. The given instance of Partition is thus a positive instance if and only if M[n, s 2] = 1 at the end of the execution. Since each entry is considered exactly once to determine its value, the time complexity of the algorithm is proportional to n(s 2+ 1) = Θ(ns). This means that the difficulty of the problem depends on the value of s, that is, on the magnitude of the values in A. In fact, let us denote by Kthe maximum element of A. If Kis polynomially bounded w.r.t. nthen also s=Pn i=1 ai≤Kn is polynomially bounded w.r.t. n, and thus the above algorithm works in polynomial time. On the other hand, if Kis exponential w.r.t. n, say K= 2n, then also sis exponential and the above algorithm works in exponential time and space. This behavior is usually referred to in the literature by telling that the Partition problem is a pseudo–polynomial NP–complete problem. The fact that in general the above algorithm is not a polynomial time algorithm for Partition can be immediately understood by comparing its time complexity with the instance size. The usual size for the instances of Partition is Θ(nlog K) (also O(nlog s) in [?, page 91]), since for conciseness every “reasonable” encoding is assumed to represent each element of Ausing a string whose length is O(log K). Here all logarithms are taken with base 2. Stated differently, the size of the instance is usually considered to be the number of bits which must be used to represent in binary all the integer numbers which occur in A. If we would represent such numbers using the unary notation, then the size of the instance would be Θ(nK). But in this case we could write a program which first converts the instance in binary form and then uses the above algorithm to solve the problem in polynomial time with respect to the new instance size. We can thus conclude that the difficulty of a numerical NP–complete problem depends also on the measure of the instance size we adopt. The fact that the difficulty of a problem generally depends upon how we measure the instance size is even more apparent if we consider the Factorization problem: Problem 1.2 Name:Factorization. •Instance: a positive integer number nwhich is the product of two prime numbers pand q •Output:p This problem is generally considered intractable, which means that no polynomial time algorithm is known that solves it on every instance. The conjectured intractability of this problem is often exploited in Cryptography: a notable example is the RSA cryptosystem [?]. Here the natural instance size for the problem is Θ(log n), the number of bits which are needed to represent nin binary form. Also for this problem, if we let the instance size be Θ(n) then the trivial algorithm which tries to divide nby every number comprised between 1 and √nis a polynomial time algorithm which solves the Factorization problem. For these reasons we believe that it is important to show that P systems which solve NP–complete numerical problems do not take their power from the fact that the instances are represented in unary notation. Hence in this paper we first propose 3 a simple method to represent positive integer numbers in binary notation using multisets of objects. Then, we propose a family of P systems which transforms this binary encoding into the unary notation used in [?,?,?,?]. The paper is organized as follows. In section 2 we introduce our encoding of binary numbers using multisets. In section 3 we propose a family of simple P systems which can be used to transform a given positive integer number from such encoding to unary notation. Section 4 concludes the paper and gives some directions for future research. 2. Encoding binary numbers using multisets First of all let us show how a given positive integer number xcan be represented in binary notation using a multiset. Let xn, xn−1,...,x1be the binary representation of x, so that x=Pn i=1 xi2i−1. We use the objects from the following alphabet: An={hb, ji|b∈ {0,1}, j ∈ {1,2,...,n}} (1) Object hb, jiis used to represent bit binto position jin the binary encoding of an integer number. Hence, to represent the above number xwe will use the following multiset (actually, a set) of objects: hxn, ni,hxn−1, n −1i,...,hx1,1i Let us remark that the alphabet Adepends on the length of the binary representation of the number x, i.e., with the alphabet Anwe can represent from 1 to 2n−1. On the other hand, the unary representation of xis obtained by choosing a symbol from an alphabet, say the symbol afrom alphabet A′, and putting into the multiset xcopies of such symbol: ax. Hence, unary notation is exponentially longer than binary notation. Our transformation thus solves another problem raised by the solutions exposed in [?,?,?,?]: in order to provide the input values to the P systems, we should insert into such systems an exponential (with respect to the instance size) number of objects. This means that an exponential amount of work to prepare the system is required. Working with binary encoded numbers, instead, allows one to prepare the system by inserting a polynomially bounded number of objects. 3. Converting from binary to unary notation In this section we propose a family of simple P systems which allows to convert a given positive integer number x, expressed in binary notation as exposed in the previous section, to the usual unary notation. The objects used by the P systems form a subset of alphabet Aof equation (??). Namely, in order to represent xin binary notation we will use only the objects which correspond to the bits of xwhich are equal to 1. For example, if x= 25 then its binary representation is 11001, and we will use the objects h1,5i,h1,4i, and h1,1i to represent it. Since the first element in the pairs of Aused is always equal to 1, 4 we can be more concise by omitting it. Once omitted the first element of the pair, also angular parenthesis are superflous. The family of P systems which performs the transformation is formally defined as follows: Π(n) = (A(n), µ, w, R(n), iin, iout) where: •A(n) = {1,2,...,n}∪{a}is the alphabet; •µ= [ ]skin is the membrane structure consisting of the skin only; •w=∅is the multiset of objects initially present in region 1; •R(n) is the following set of evolution rules associated with region 1: [j→(j−1)2]skin for all j∈ {2,3,...,n} [1 →a]skin •iin =skin specifies the input membrane of Π; •iout =skin specifies the output membrane of Π. The semantics of the rules is the usual for evolution rules. All they are applied in a maximal parallel mode. The number of cellular steps of the P system is bounded by nand the computation halts when no more rules can be applied. When this happens, the multiset placed in the output membrane (the only one membrane) is the output of the computation. Computations proceed as follows. The objects which denote the positions of 1’s in the binary representation of xare initially put into the region enclosed by the skin. Then the computation starts, and the rules from Rare applied. It is easily seen that the presence of object j, with j∈ {1,2,...,n}, will produce 2j−1copies of object a. Hence at the end of the computation, when no more rules from Rcan be applied, the skin will contain xcopies of object a, that is, the unary representation of x. We conclude this section with an example of computation of the above P systems. Let us consider again the value x= 25; as previously said, it will be represented by means of objects 5, 4, and 1 (each in a unique copy). At the first step of computation, we apply in parallel the rules 1 →a, 4 →3,3 and 5 →4,4, obtaining the multiset a, 3,3,4,4. Then, we apply in parallel the rule 3 →2,2 on each copy of the symbol 3, thus obtaining four copies of the symbol 2, and the rule 4 →3,3 on each copy of the symbol 4, thus obtaining four copies of the symbol 3. The multiset we obtain after the second step of computation will be a, 2,2,2,2,3,3,3,3. Hence, we apply the rules 2 →1,1 and 3 →2,2 obtaining a, 18,28. By means of the rules 1 →aand 2 →1,1 we then obtain the multiset a9,116 and finally, applying again 1 →awe obtain the multiset a25 which is exactly the unary codification of the initially binary coded number. 5 From the previous definition and example, it is easy to see that the cardinality of the alphabet and the number of computation steps are linear with respect to the input size. 4. Composition of P systems In the previous section, a method for converting natural number from binary into unary notation has been described. Intuitively, such a P system could be composed with a P system which solves an instance of a problem with input in unary form and to get a new P system which solves the same problem with input in binary form. The formalization of such intuition has several technical details and, to the best of our knowledge, the composition of P systems has not been defined. In this section we present a definition for composing P systems which fit into our purposes. The general definition and the study of its properties lies out of the scope of this paper. First we define a joint of two P systems Ajoint P1◦P2of P systems P1and P2is a new P system where the skin membrane of P2is identified to an elementary membrane of P1. In this way we obtain a new labelled membrane structure. Each labelled membrane keeps its initial multiset and set of rules. In the initial configuration, the new membrane obtained by identification, the initial multiset and set of rules are the union of the multisets and sets of rules of the identified membranes. Next we give a formal definition. Definition 1 Let P1= (O1, H1, EC1, µ1, w1 1,...,w1 m1, R1)and P2= (O2, H2, EC2, µ2, w2 1, . . . , w2 m2, R2)be two P systems where: m1, m2≥1are the initial degrees of the systems; O1and O2are the alphabets of objects; H1and H2 are two disjoint finite set of labels for membranes; EC1=EC2are the finite sets of electrical charges for membranes; µ1and µ2are the membrane structures consisting (resp.) of m1and m2membranes labelled (not necessarily in a one-to-one manner) with elements of H1and H2;wi 1,...,wi mare strings over Oi, describing the multisets of objects placed in the miregions of µi(for i=1,2); R1and R2are the finite sets of rules associated to P1and P2. Let i1be the label of an elementary membrane of P1and s2the label of the skin membrane of P2. And let µbe the membrane structure obtained by identifying i1 with s2. Since the none i1is a leave in µ1and the node s2is the root of µ2the new graph is also a membrane structure. We keep the same label for all membranes and label the joint membranes by α. We define a joint P1◦P2as a P system P1◦P2= (O, H, EC, µ, w1,...,wm, R) where m=m1+m2−1is the initial degree of the systems; O=O1∪O2is the alphabet of objects; H= (H1−{i1})∪(H2−{s2})∪{α}is the finite set of labels for membranes; EC =EC1=EC2is the finite set of electrical charges for membranes; µand is the membrane structure labelled with elements of H;w1,...,wkare strings over O, describing the multisets of objects placed in the mregions of; R=R1∪R2 is the finite set of rules. 6 Note that given two P systems with the same set of electrical charges (which can be empty) there exists several posibilities of getting a joint: One for each elementary membrane of P1. Next we define the composition of two P systems. In order to define such composition we need two P systems with input and output. Definition 2 Let P1and P2be two P systems with input and output such that: •The input membrane of P1is an elementary membrane. We will denote by i1 the label of such membrane. •The output membrane of P2is the skin membrane. We will denote by s2the label of such membrane. The composition P1◦P2is the joint obtained by identifying i1with s2. Note that if P2sends the output to the environment, we can consider a new external membrane surrounding the whole P system which becomes the new skin. With this new skin we can consider the composition with another P system. 5. A Case Study In this section we describe two familes of P systems ΠBans Ppart: •The family ΠB={PB(n, d) : n, d ∈N}converts multisets of natural numbers from binary into unary notation. The P system PB(n, d) depends on the number of elements that we want to convert and on d, where dis defined by d=Ent[log2(max A)] + 1 (2) where Ais the set of numbers to convert. •The family Πpart ={Ppart(n) : n, ∈N}is a uniform family which solves the NP-problem Partition. It is based on the solution presented in ... but with small changes. Each P system Ppart(n) solves all instances of the problem with nelements. The solution is obtained in polynomial time on nand the input has to be provided in unary form. Both families are designed with input and output and it has sense to consider the composition of P systems of both families. We obtain the following family: Π = {Ppart(n)◦PB(n, d) : n, d ∈N} where each P system P(n, d) = Ppart(n)◦PB(n, d) is a cellular device which solves all the instances of the Partition problem with the same parameters nand d. 5.1. The family ΠB The P systems of this family are adapted from the model presented in the section ??. The differences are mainly two: Two membranes are considered, one as input membrane and the second one (the skin) is the output membrane. In this way we prepare the composition with P systems of the second family. 7 The second difference is due to technical reasons. We add new elements which has no meaning in the encoding of the information, but they make sense after the composition (objects e0,zand f) and a counter v1. The problem can be stated as follows: Given a multiset Aof natural numbers expressed in binary form, to get a multiset A′with such numbers expressed in binary form. We adapt the description from section refsec:enc. Instead of codifying a single natural number, we look for a P system which convert a multiset of numbers. So, for each element in the multiset, we consider a mark {x1, x2,...}, so in this way, following section ?? the multiset {3,4,3,11}can be expressed in binary form as the set of pairs {(x1,1),(x1,1),(x2,3),(x3,1),(x3,2),(x4,1)(x4,2),(x4,4)} where (xi, j) represents that the i−th element in the enumeration of the multiset has one in the j−th position of the binary representation. We define the family ΠB={PB(n, d) : n, d ∈N}where each PB(n, d) solves all the instances of the problem with the same number of elements nand the same bound d, defined in the equation ??. (In fact, these nand dare upper bounds). The P system PB(n, d) = (O(n, d), H, EC, µ, wt, ws,...,R(n, d)) is defined as follows: •O(n, d) = {e0, z, f}∪{y1,...,yn}∪{v1,...,vd+1} ∪ {(xi, j) : 1 ≤i≤n, 1≤j≤d} •H={t, s}with tthe label of the input membrane and s, the skin the label of the output membrane. •EC =∅(We can also consider the membranes with neutral charge along all the computation) •µ= [ [ ]t]s •wt={e0, f, v1};ws=∅ •The following set of rules R(n, d): [(xi, j)→(xi, j −1)]tfor all i∈ {1,...n}and j∈ {1,...,d}. [(xi,1) →yi]tfor all i∈ {1,...n}. [vj→vj+1]tfor all j∈ {1,...,d}. [vd+1]t→z. All the rules are associated to the label tand are object evolution rule. The only exception is the last one, which is a dissolution rule. At the beginning of the computation, the input codifying the multiset of natural numbers in binary form (as described above) is placed in the input membrane. The P system evolves as described in section ??. After dsteps the membrane tcontains the elements e0,f,vd+1 and a multiset of elements yi, 1 ≤i≤ncodifying the input. In the next step vd+1 dissolves the membrane tand is transformed into zin 8 the skin. The remaining objects also go to the skin. No more rules can be applied and the computation halts. The computation is deterministic and halts after d+ 1 steps. 5.2. The family Πpart This family is a uniform familycof P systems in the framework of active membranes (see ...) which solves the NP-problem Partition. It is based on the solution presented in ... but with small changes. Each P system Ppart(n) solves all instances of the problem with nelements. The solution is obtained in polynomial time on nand the input has to be provided in unary form. Each P sysstem of the family, Ppart(n), n, ∈Nconsists on the following elements: •O(n) = {a0, a, b0, b, c, d0, d1, d2, f, g, g0, g1, h0, h1, p0, p, q, z, #, yes, no, no0} ∪ {e0,...,en}∪{i1, i2, i3, i4}∪{x1,...,xn}∪{y1,...,yn}∪{z1,...,z2n+1} •H={e, r, s}; the skin s, the label efor the working membranes and a label r for the membrane of control. •EC ={+,−,0} •µ= [ [ ]r[ ]e]s •we=∅;ws=∅;wr={b0, h0} •The set of rules R(n) described below. We follow the design for solving PARTITION with active membranes presented in ..., with small changes due to technical reasons. A detailed description and motivation for the rules can be found there. cIn the sense of ... 9