On Descriptive Complexity of P Systems

On Desc ip i e Complexi y o P Sys ems Miguel A. Gu i´e ez-Na anjo, Ma io J. P´e ez-Jim´enez, and Agus in Riscos-N´u˜nez Resea ch G oup on Na u al Compu ing, Depa men o Compu e Science and A ificial In elligence, Uni e si y o Se illa, A da. Reina Me cedes s/n, 41012 Se illa, Spain {magu ie , ma pe , a iscosn}@us.es Abs ac . In his pape we add ess he p oblem o desc ibing he com- plexi y o he e olu ion o a P sys em. This issue is is specially ha d in he case o P sys ems wi h ac i e memb anes, whe e he numbe o s eps o a compu a ion is no sufficien o e alua e he complexi y. Se illa ca - pe s we e in oduced in [1], and hey desc ibe he space- ime complexi y o P sys ems. Based on hem, we define some new pa ame e s which can be used o compa e e olu ions o P sys ems. To illus a e his, we also include wo diffe en cellula solu ions o he Subse Sum p oblem and compa e hem ia hese new pa ame e s. 1 In oduc ion The e olu ion o a P sys em is a complex p ocess whe e (possibly) a la ge numbe o symbol-objec s, memb anes and ules a e in ol ed. In he case o P sys ems wi h ac i e memb anes, he p oblem o desc ibing he complexi y o he com- pu a ional p ocess becomes specially ha d. In his case, elemen a y memb anes can di ide in o wo new memb anes and, due o he pa allelism in insic o P sys ems, an exponen ial numbe o memb anes can be ob ained in polynomial ime. This ea u e makes P sys ems wi h ac i e memb anes a powe ul ool o a ack NP-comple e p oblems and, indeed, se e al efficien solu ions o his ype o p oblems ha e been p esen ed (see, e.g., [4, 9, 10, 11] o [12]). These solu ions a e p oposed in he amewo k o ecognize P sys ems wi h ex e nal ou pu , and hey p esen significan simila i ies among hem. The basic idea in hese designs is he c ea ion o an exponen ial numbe o memb anes (wo kspace) in poly- nomial ime and he use o each memb ane as an independen compu a ional de ice. All memb anes e ol e in pa allel and he compu a ion has a polynomial cos in ime. The p ocess ends wi h a final s age (wi h polynomial cos ) ha checks he answe s o hese de ices and sends an ou pu o he en i onmen . The complexi y in ime ( he numbe o cellula s eps) o hese solu ions is polynomial, bu i is clea ha he ime is no he unique a iable ha we need o conside in o de o e alua e he complexi y o he p ocess. Ciobanu, P˘aun and ¸S e ˘anescu p esen ed in [1] a new way o desc ibe he complexi y o a compu a ion in a P sys em. The so-called Se illa ca pe is an ex ension o he no ion o Szila d language om g amma s o he case when se e al ules a e used a he same ime. In his pape we make use o Se illa ca pe s o desc ibe he compu a ions o P sys ems ha sol e he Subse Sum p oblem. Two amilies o ecognize P sys ems ha e been designed ha need a polynomial ime o send an ou pu o he en i onmen . We p esen hei co esponding Se illa ca pe s in o de o compa e hem, and hen some ideas o imp o e he design o P sys ems o sol ing o he new p oblems a e p oposed. The pape is o ganized as ollows. In Sec ion 2 we fi s gi e some p elimina y no ions abou ecognize P sys ems and a polynomial complexi y class on P sys- ems is defined. Sec ion 3 p esen s he Se illa ca pe s and some new pa ame e s ela ed wi h hem a e in oduced in Sec ion 4. Finally, we use hese pa ame e s o compa e wo solu ions o he Subse Sum p oblem. 2 P elimina ies Roughly speaking, a P sys em consis s o a cell-like memb ane s uc u e, in he compa men s o which one places mul ise s o objec s which e ol e acco ding o gi en ules in a synch onous non-de e minis ic maximally pa allel manne . Defini ion 1. AP sys em wi h inpu is a uple (Π,Σ,iΠ), whe e: ΠisaP sys em, wi h wo king alphabe Γ, wi h pmemb anes labelled by 1,...,p, and ini ial mul ise s M1,...,Mpassocia ed wi h hem; Σis an (inpu ) alphabe s ic ly con ained in Γ; he ini ial mul ise s a e o e Γ−Σ; finally, iΠis he label o a dis inguished (inpu ) memb ane. The compu a ions o a P sys em wi h inpu a mul ise mo e Σ, a e defined in a na u al way. The only no el y is ha he ini ial configu a ion mus be he ini ial configu a ion o he sys em o which he inpu mul ise mis added o he mul ise om egion iΠ. Defini ion 2. Le (Π,Σ,iΠ)be a P sys em wi h inpu . Le Γbe he wo king alphabe o Π,µ he memb ane s uc u e and M1,...,Mp he ini ial mul ise s o Π.Le mbe a mul ise o e Σ. The ini ial configu a ion o (Π,Σ,iΠ) wi h inpu mis (µ, M1,...,MiΠ∪m,...,Mp). In he case o P sys ems wi h inpu and wi h ex e nal ou pu , he concep o compu a ion is as s anda d in memb ane compu ing, wi h a mino diffe ence which will be explained below. We conside ha i is no possible o obse e he in e nal p ocesses inside he P sys em and we can only know i he compu a ion has hal ed ia some dis inguished objec s sen ou o he skin. We can o malize hese ideas in he ollowing way. 2.1 Recognize P Sys ems Recall ha a decision p oblem Xis a pai (IX,θ X) such ha IXis a language o e a fini e alphabe (whose elemen s a e called ins ances) and θXis a o al boolean unc ion o e IX. In o de o sol e decision p oblems we need P sys ems wi h inpu such ha all hal ing compu a ions s a ing om an ini ial configu a ion wi h a gi en inpu mul ise (encoding an ins ance o he p oblem) p oduce he same ou pu . The sys ems o his ype will be called ecognize P sys ems. Defini ion 3. A ecognize P sys em is a P sys em wi h inpu , (Π,Σ,iΠ), and wi h ex e nal ou pu such ha : 1. The wo king alphabe con ains wo dis inguished elemen s YES, NO. 2. All compu a ions hal . 3. I Cis a compu a ion o Π, hen ei he objec YES o objec NO (bu no bo h) mus ha e been eleased in o he en i onmen , and only in he las s ep o he compu a ion. We say ha Cis an accep ing compu a ion ( espec i ely, ejec ing compu a ion) i he objec YES ( espec i ely, NO) appea s in he en i onmen associa ed wi h he co esponding hal ing configu a ion o C. The abo e defini ions a e s a ed in a gene al way, bu in his pape P sys ems wi h ac i e memb anes will be used. We e e o [8] (see chap e 7) o a de ailed defini ion o e olu ion ules, ansi ion s eps, configu a ions and compu a ions in his model. We deno e by AM he class o all ecognize P sys ems wi h ac i e mem- b anes. 2.2 The Compu a ional Complexi y Class PMCF The fi s esul s abou “sol abili y” o NP–comple e p oblems in polynomial ime (e en linea ) by cellula compu ing sys ems wi h memb anes we e ob ained using a ian s o P sys ems ha lack an inpu memb ane (see e.g. [7] o [14]). Thus, he cons uc i e p oo s o such esul s need o design one sys em o each ins ance o he p oblem. I we wan ed o pe o m such a solu ion o some decision p oblem in a labo- a o y, we will find a d awback on his app oach: a sys em cons uc ed o sol e a conc e e ins ance is useless when ying o sol e ano he ins ance. This sho - coming can be easily o e aken i we conside a P sys em wi h inpu . Then, a sys em could sol e diffe en ins ances o he p oblem, p o ided ha he co e- sponding inpu mul ise s a e in oduced in he inpu memb ane. Ins ead o looking o a single sys em ha sol es a p oblem, we p e e de- signing a amily o P sys ems such ha each elemen decides all he ins ances o “equi alen size”, in ce ain sense. Defini ion 4. Le Fbe a class o ecognize P sys ems. We say ha a deci- sion p oblem X=(IX,θ X)is sol able in polynomial ime by a amily Π= (Π(n))n∈N+o ype F, and we deno e his by X∈PMCF, i he ollowing is ue: –The amily Πis polynomially uni o m by Tu ing machines; ha is, he e exis s a de e minis ic Tu ing machine cons uc ing Π(n) om n∈N+in polynomial ime. –The e exis s a pai (g,h)o polynomial- ime compu able unc ions g:L→ n∈N+IΠ(n)and h:L→N+such ha o e e y u∈Lwe ha e g(u)∈IΠ(h(u)), and •The amily Πis polynomially bounded wi h ega d o (g,h); ha is, he e exis s a polynomial unc ion p, such ha o each u∈IXe e y compu- a ion o Π(h(u)) wi h inpu g(u)is hal ing and, mo eo e , i pe o ms a mos p(|u|)s eps. •The amily Πis sound, wi h ega d o (X,g,h); ha is, o each u∈IX i is e ified ha i he e exis s an accep ing compu a ion o Π(h(u)) wi h inpu g(u), hen θX(u)=1. •The amily Πis comple e, wi h ega d o (X, g, h); ha is, o each u∈ IXi is e ified ha i θX(u)=1, hen e e y compu a ion o Π(h(u)) wi h inpu g(u)is an accep ing one. In he abo e defini ion we ha e imposed e e y P sys em Π(n) obeconfluen ,in he ollowing sense: e e y compu a ion wi h he same inpu p oduces he same ou pu . F om he dfini ion, one can easily p o e ha he class PMCFis closed unde polynomial– ime educ ion and complemen . 3 Se illa Ca pe s Se illa ca pe s we e p esen ed in [1] as an ex ension o he Szila d language, which consis s o all s ings o ule labels desc ibing co ec de i a ions in a gi en g amma (see, e.g., [5, 6] o [13]). The Szila d language is usually defined o g amma s in he Chomsky hie a chy whe e only a single ule is used in each de i a ion s ep, so a de i a ion can be ep esen ed as he s ing o he labels o he ules used in he de i a ion ( he labelling is supposed o be one- o-one). Se illa ca pe s a e a Szila d-way o desc ibe a compu a ion in a P sys em. The main diffe ence is ha now a mul ise o ules can be used in each e olu ion s ep o a P sys em. In [1] a bidimensional w i ing is p oposed o desc ibe a compu a ion o a P sys em. The (Se illa) ca pe associa ed wi h a compu a ion o a P sys em is a able wi h he ime on he ho izon al axis and he ules explici ly men ioned along he e ical axis; hen, o each ule, in each s ep, a piece o in o ma ion is gi en. Depending on he amoun o in o ma ion gi en o desc ibe he e olu ion, Ciobanu, P˘aun, and S¸ e ˘anescu p opose fi e a ian s o he Se illa ca pe s: 1. Speci ying in each ime uni o each memb ane whe he a leas one ule was used in i s egion o no . 2. Speci ying in each ime uni o each ule whe he i was used o no . 3. Men ioning in each ime uni he numbe o applica ions o each ule; his is 0 when he ule is no used and can be a bi a ily la ge when he ules a e dealing wi h a bi a ily la ge mul ise s. 4. We can also dis inguish h ee cases: ha a ule canno be used, ha a ule can be used bu i is no because o he nonde e minis ic choice, and ha a ule is ac ually used. 5. A u he possibili y is o assign a cos o each ule, and o mul iply he numbe o imes a ule is used wi h i s cos . They also p opose wo pa ame e s (weigh and su ace) o s udy Se illa ca pe s. In his pape we popose wo new pa ame e s (heigh and a e age weigh ) ha will be desc ibed in he nex sec ion. 4 Pa ame e s o he Desc ip i e Complexi y Many imes we a e no in e es ed only in he numbe o cellula s eps o he compu a ion, bu also in o he ypes o esou ces equi ed o pe o m he com- pu a ion. Especially i we wan o implemen in silico a P sys em, we need o be ca e ul wi h he numbe o imes ha a ule is applied, maybe wi h he numbe o memb anes and/o he numbe o objec s p esen in a gi en configu a ion. In o de o desc ibe he complexi y o he compu a ion, he ollowing pa am- e e s a e p oposed: – Weigh : I is defined in [1] as he sum o all he elemen s in he ca pe , i.e., as he o al numbe o applica ions o ules along he compu a ion. The applica ion o a ule has a cos and he weigh measu es he o al cos o he compu a ion. – Su ace: This is he mul iplica ion o he numbe o s eps by he o al numbe o he ules used by he P sys em. I can be conside ed as he po en ial size o he compu a ion. F om a compu a ional poin o iew we a e no only in e es ed in P sys ems which hal in a small numbe o s eps, bu in P sys ems which use a small amoun o esou ces. The su ace measu es he esou ces used in he design o he P sys em. G aphically, i ep esen s he su ace whe e he Se illa ca pe lies on. – Heigh : This is he maximum numbe o applica ions o any ule in a s ep along he compu a ion. G aphically, i ep esen s he highes poin eached by he Se illa ca pe . – A e age Weigh : I is calcula ed by di iding he weigh o he su ace o he Se illa ca pe . This concep p o ides a ela ion be ween bo h pa ame e s, and gi es an indica ion on how he P sys em exploi s i s massi e pa allelism. 5 Compa ing Two Solu ions o he Subse Sum P oblem The Subse Sum p oblem is he ollowing one: Gi en a fini e se A, a weigh unc ion, w:A→N, and a cons an k∈N, de e mine whe he o no he e exis s a subse B⊆Asuch ha w(B)=k. We will use a uple (n, (w1,...,w n),k) o ep esen an ins ance o he p ob- lem, whe e ns ands o he size o A={a1,...,a n},wi=w(ai), and kis he cons an gi en as inpu o he p oblem. We p opose he e wo solu ions o his p oblem based on a b u e o ce algo- i hm implemen ed in he amewo k o P sys ems wi h ac i e memb anes. The idea o he design is be e unde s ood i we di ide he solu ion o he p oblem in o se e al s ages: –Gene a ion s age: o e e y subse o A, a memb ane is gene a ed ia mem- b ane di ision. –Weigh calcula ion s age: in each memb ane he weigh o he associa ed subse is calcula ed. This s age will ake place in pa allel wi h he p e ious one. –Checking s age: in each memb ane i is checked whe he o no he weigh o i s associa ed subse is exac ly k. This s age canno s a in a memb ane be o e he p e ious ones a e o e in ha memb ane. –Ou pu s age: when he p e ious s age has been comple ed in all memb anes, he sys em sends ou he answe o he en i onmen . Fi s Design Nex we p esen a amily o ecognize P sys ems sol ing Subse Sum, acco ding o Defini ion 4. This amily can be ound in [9]. Fi s , we conside a polynomial– ime compu able and bijec i e unc ion om N2on o N( o example, x, y=((x+y)(x+y+1)/2)+y). Fo each (n, k)∈N2 we conside he P sys em (Π1(n, k),Σ(n, k),i(n, k)), whe e he inpu alphabe is Σ(n, k)={x1,...,x n}, he inpu memb ane is i(n, k)=eand Π1(n, k)= (Γ(n, k),{e, s},µ,Me,Ms,R) is defined as ollows: •Alphabe : Γ(n, k)=Σ(n, k)∪{¯a0,¯a, a0,a,d +,e 0,...,e n,q,q 0,...,q 2k+1, z0,...,z 2n+2k+2, Y es, no, No, #}. •memb ane s uc u e: µ=[[] e]s. •Ini ial mul ise s: Ms=z0;Me=e0¯ak. •The se Ro e olu ion ules consis s o he ollowing ules: (a)[ei]0 e→[q]− e[ei]+ e, o i=0,...,n. [ei]+ e→[ei+1]0 e[ei+1]+ e, o i=0,...,n−1. (b)[x0→¯a0]0 e;[x0→λ]+ e;[xi→xi−1]+ e, o i=1,...,n. (c)[q→q0]− e;[¯a0→a0]− e;[¯a→a]− e. (d)[a0]− e→[] 0 e#; [a]0 e→[] − e#. (e)[q2j→q2j+1]− e, o j=0,...,k. [q2j+1 →q2j+2]0 e, o j=0,...,k−1. ( )[q2k+1]− e→[] 0 eYes;[q2k+1]0 e→[] 0 e#. [q2j+1]− e→[] − e#, o j=0,...,k−1. (g)[zi→zi+1]0 s, o i=0,...,2n+2k+1; [z2n+2k+2 →d+no]0 s. (h)[d+]0 s→[] + sd+;[no →No]+ s;[Yes]+ s→[] 0 sYes;[No]+ s→[] 0 sNo. Le us ecall ha he ins ance u=(n, (w1,...,w n),k) is p ocessed by he P sys em Π1(n, k) wi h inpu he mul ise xw1 1xw2 2...x wn n. This design depends on he wo cons an s ha a e gi en as inpu in he p oblem: nand k. I consis s on 5n+5k+18 e olu ion ules, and i an ap op ia e inpu mul ise is in oduced inside memb ane ebe o e s a ing he compu a ion, he sys em will s op and ou pu an answe in 2n+2k+ 6 s eps (i he answe is No)o in2n+2k+ 5 s eps (i he answe is Yes). Acco ding o Defini ion 4 and using he abo e amily o P sys ems, we can p o e ha , Subse Sum ∈PMCAM (see [9], o de ails). Second Design Nex we p esen a new amily o ecognize P sys ems sol ing Subse Sum, inspi ed in he p e ious one. Some modifica ions a e made ollowing he design p esen ed in [3]. Fo each n∈Nwe conside he P sys em (Π2(n),Σ(n),i(n)), whe e he inpu alphabe is Σ(n)={x1,...,x n}, he inpu memb ane is i(n)=eand Π2(n)=(Γ(n),{e, , s},µ,Me,M ,Ms,R) is defined as ollows: •Alphabe : Γ(n)=Σ(n)∪{¯a0,¯a, a0,a,c,d 0,d 1,d 2,e 0,...,e n,g,¯g, ˆg,h0,h 1, q,q0,q 1,q 2,q 3, Y es, No, no, z0,...,z 2n+1,#}. •Memb ane s uc u e: µ=[[] e]s. •Ini ial mul ise s: Ms=z0;Me=e0g¯ak;M =h0b. •The se Ro e olu ion ules consis s o he ollowing ules: (a)[ei]0 e→[q]− e[ei]+ e, o i=0,...,n. [ei]+ e→[ei+1]0 e[ei+1]+ e, o i=0,...,n−1. (b)[x0→¯a0]0 e;[x0→λ]+ e;[xi→xi−1]+ e, o i=1,...,n. (c)[q→q0]− e;[¯a0→a0]− e;[¯a→a]− e. [g]− e→[] − e¯g. [en]+ e→#. [¯a0→λ]0 s;[¯a→λ]0 s;[g→λ]0 s. [a→λ]+ e;[a0→λ]+ e. (d)[a0]− e→[] 0 e#; [a]0 e→[] − e#. (e)[q0→q1]− e;[q1→q0]0 e. [q0]0 e→[] + eno. [q1→q2c]− e;[q2→q3]0 e;[c]− e→[] 0 ek. ( )[q3]0 e→[] + eYes;[q3]− e→[] + eno. (g)[zi→zi+1]0 s, o i=0,...,2n;[z2n+1 →d0d1]0 s. d0[] 0 →[d0]− ;[d1]0 s→[] + sd1. (de )[h0→h1]− ,[h1→h0]+ , [b]− →[] + b,ˆg[] + →[ˆg]− , b[] − →[b]+ ,[ˆg]+ →[] − ˆg, [h0]+ →[] + d2,[d2]+ s→[] − sd2. (h)[ no →No]− s;[Yes]− s→[] 0 sYes;[No]− s→[] 0 sNo. In his solu ion he ins ance u=(n, (w1,...,w n),k) is p ocessed by he P sys em Π2(n) wi h inpu he mul ise xw1 1xw2 2...x wn n. The abo e design depends only on one o he cons an s ha a e gi en as inpu in he p oblem: n. I is qui e simila o he p e ious one, he diffe ence lies in he checking s age and he answe s age. In his case we a oid he use o coun e s ha equi e knowing he cons an k. The numbe o e olu ion ules is 5n+ 41, and he numbe o s eps o he compu a ion depends on he conc e e ins ance ha we need o sol e, bu i is linea ly bounded. Desc ip i e Complexi y We p esen some de ailed s a is ics abou he p e ious designs, ying o compa e hem on a mo e gene al basis han jus looking he numbe o s eps ha he compu a ion pe o ms. Following his scheme, we p esen he Se illa ca pe s associa ed wi h he compu a ions o he wo diffe en solu ions o he Subse Sum p oblem wo king on he same ins ance: u=(5,(3,5,3,2,5),9). Tha is, n=5,k= 9, and he lis o weigh s is w1=3,w 2=5,w 3=3,w 4=2,w 5=5. The inpu mul ise is hen: x3 1x5 2x3 3x2 4x5 5. 0 10 20 30 40 50 60 70 80 90 Rules 0510 15 20 25 30 35 S eps Fig. 1. Se illa ca pe o solu ion 1 The P sys em Π1(5,9) has 88 e olu ion ules, and all o hem a e applied wi h he excep ion o he ules: [q19]− e→[] 0 eYes,[q3]− e→[] − e#, [q9]− e→[] − e# and [Yes]− s→[] 0 sYes. The P sys em Π1(5,9) s ops a s ep 33 and sends an objec No o he en i onmen . The weigh o he Se illa ca pe ( he o al numbe o ule applica ions along he compu a ion) is 2179, and i s heigh ( he maximal numbe o imes ha a ule is applied in one e olu ion s ep) is 82 and i is eached a S ep 9 by he ule [¯a0→a0]− e. The su ace o he Se illa ca pe is 2904, and i s a e age weigh is 0.749656 010203040506070 Rules 0510 15 20 25 30 35 40 S eps Fig. 2. Se illa ca pe o solu ion 2 The P sys em Π2(5) has 65 e olu ion ules, and all o hem a e applied wi h he excep ion o he ules: [q3]0 e→[] + eYesand [Yes]− s→[] 0 sYes. The P sys em Π2(5) s ops a s ep 38 and sends an objec No o he en i onmen . The weigh o he Se illa ca pe is 3368, and i s heigh is 108, his heigh is eached a S ep 10 by he ule [¯a0→λ]0 s. The su ace o he Se illa ca pe is 2470, and i s a e age weigh is 1.36275 The ollowing able shows he pa ame e s o bo h solu ions: Solu ion 1 Solu ion 2 Rules 88 65 S eps 33 38 Su ace 2904 2470 Weigh 2179 3368 Heigh 82 108 A e age Weigh 0.749656 1.36275 I we conside he numbe o s eps as a complexi y measu e o compa e bo h designs, hen we conclude ha he fi s solu ion is be e han he second one (al hough no asymp o ically), since i needs less s eps. Mo eo e , conce ning he weigh o he Se illa ca pe , solu ion 1 is again be e han solu ion 2, because i uses less esou ces du ing he compu a ion. Howe e , he ac ha he a e age weigh o solu ion 2 is la ge han he a e age weigh o solu ion 1 can be in e p e ed by saying ha he second design makes a be e use o he pa allelism in P sys ems ( he compu a ion is mo e in ense). We would like o ema k ha hese a e no asymp o ical compa isons, as we ocus only on he da a co esponding o one ins ance. Indeed, due o he expo- nen ial numbe o memb anes c ea ed du ing he gene a ion s age, we belie e ha conside ing ano he ins ance wi h a g ea e size will s ess he diffe ences be ween he design based only on nand he o he one, based on bo h nand k. The bound on he size o he in ances ha can be s udied is imposed by he