Monodirectional P Systems

Monodi ec ional P Sys ems? Albe o Lepo a i, Luca Manzoni, Gianca lo Mau i, An onio E. Po eca, Claudio Zand on Dipa imen o di In o ma ica, Sis emis ica e Comunicazione Uni e si `a degli S udi di Milano-Bicocca Viale Sa ca 336/14, 20126 Milano, I aly {lepo a i,luca.manzoni,mau i,po eca,zand on}@disco.unimib.i Summa y. We in es iga e he in luence ha he low o in o ma ion in memb ane sys ems has on hei compu a ional complexi y. In pa icula , we analyse he beha iou o P sys ems wi h ac i e memb anes whe e communica ion only happens om a memb ane owa ds i s pa en , and ne e in he opposi e di ec ion. We p o e ha hese “monodi ec ional P sys ems” a e, when wo king in polynomial ime and unde s anda d complexi y- heo e ic assump ions, much less powe ul han un es ic ed ones: indeed, hey cha ac e ise classes o p oblems de ined by polynomial- ime Tu ing machines wi h NP o acles, a he han he whole class PSPACE o p oblems sol able in polynomial space. 1 In oduc ion P sys ems wi h ac i e memb anes wo king in polynomial ime a e known o be able o sol e all PSPACE -comple e p oblems [ 1 ]; his exploi s memb ane s uc u es o polynomial dep h and a bidi ec ional low o in o ma ion (in e ms o mo ing objec s o changing cha ges), bo h om a pa en memb ane o i s child en, and he in opposi e di ec ion. When es ic ing he dep h o he memb ane s uc u es o a amily o P sys ems o a cons an amoun , i is s ill possible o sol e p oblems in he coun ing hie - a chy CH , de ined in e ms o polynomial- ime Tu ing machines wi h o acles o coun ing p oblems [ 4 ]. In he p oo o his esul , i has been no iced ha send-in communica ion ules o he o m a [ ] α h→ [ b ] β h allow us o check whe he he amoun o objec s loca ed in a memb ane exceeds a (possibly exponen ial) h eshold in polynomial ime. I is hen na u al o ask whe he ha ea u e is ac ually necessa y in o de o ob ain he powe o coun ing in polynomial ime. In his pape we p o e (unde he s anda d complexi y- heo e ic assump ion ha PNP 6 = P#P ) ha his is ac ually ? This wo k was pa ially suppo ed by Uni e si `a degli S udi di Milano-Bicocca, FA 2013: “Complessi `a compu azionale in modelli di calcolo bioispi a i: Sis emi a memb ane e sis emi di eazioni”. 208 A. Lepo a i e al. he case: P sys ems wi h monodi ec ional communica ion, whe e he in o ma ion lows only owa ds he ou e mos memb ane, a e limi ed o PNP , he class o p oblems e icien ly sol ed by Tu ing machines wi h NP o acles. This happens e en when allowing polynomially deep memb ane s uc u es, a weak o m o non- elemen a y memb ane di ision, o dissolu ion (which, in his case, u ns ou o be as powe ul as weak non-elemen a y di ision). The PNP uppe bound is ac ually eached when dissolu ion o weak non-elemen a y di ision a e allowed; i nei he is a ailable, hen he compu a ion powe dec eases o PNP k , whe e he que ies mus all be ixed in ad ance, a he han asked adap i ely. Chap e 17 o Papadimi iou’s book [ 7 ] p o ides mo e de ails on complexi y classes de ined in e ms o Tu ing machines wi h NP o acles. Fo an in oduc ion o P sys ems wi h ac i e memb anes ( AM ), we e e he eade o he o iginal pape by Gh. P˘aun [ 8 ], supplemen ed by he de ini ions o complexi y classes PMCAM ( esp., PMC? AM ) o p oblems sol ed by uni o m ( esp., semi-uni o m) amilies o con luen P sys ems in polynomial ime [ 5 ]. De- ine M = AM(−i,−n,+wn) o be he class o monodi ec ional P sys ems wi h ac i e memb anes, wi hou send-in ules; we also emo e he usual (“s ong”) non-elemen a y di ision ules, o he o m [ ]+ h1· · · [ ]+ hm[ ]− hm+1 · · · [ ]− hnα h→[ ]δ h1· · · [ ]δ hmβ h[ ]ζ hm+1 · · · [ ]ζ hnγ h since hey also p o ide a way o memb ane h o sha e in o ma ion wi h i s child en by changing hei cha ge. We eplace hese ules by “weak” non-elemen a y di ision ules [ 11 ] o he o m [ a ] α h→ [ b ] β h [ c ] γ h , which allow he c ea ion o complex memb ane s uc u es (such as comple e bina y ees) wi hou exchanging in o ma ion wi h he child en memb anes. Le M(−d) , M(−wn) , and M(−d,−wn) deno e monodi ec ional P sys ems wi hou dissolu ion, wi hou weak non-elemen a y di ision, and wi hou bo h kinds o ules, espec i ely. Fo each class D o P sys ems, le PMCD and PMC? D be he classes o p oblems sol able by uni o m and semi-uni o m amilies o P sys ems o class D. Then, he main esul s o his pape can be summa ised as ollows: • The whole class PMC[?] M , as well as PMC[?] M(−d) and PMC[?] M(−wn) , a e equi a- len o PNP. He e [?] deno es op ional semi-uni o mi y. •The class PMC[?] M(−d,−wn) is equi alen o PNP k. The es o he pape is s uc u ed as ollows: in Sec ion 2 we p o e some basic limi a ions o monodi ec ional P sys ems; in Sec ion 3 we exploi hese esul s o p o e uppe bounds o he complexi y classes o monodi ec ional P sys ems; in Sec ion 4 we p o ide he co esponding lowe bounds by simula ing Tu ing machines wi h NP o acles; in Sec ion 5 some esul s o he p eceding sec ions a e imp o ed; inally, in Sec ion 6 we p esen some open p oblems and di ec ions o u u e esea ch. Monodi ec ional P Sys ems 209 2 P ope ies o monodi ec ional P sys ems We begin by p o ing some p ope ies o monodi ec ional P sys ems ha show how he lack o inbound communica ion subs an ially es ic s he ange o beha iou s exhibi ed du ing he compu a ions. De ini ion 1. Le Π be a P sys em, and le C and D be con igu a ions o Π . We say ha C is a es ic ion o D , in symbols C D , i he memb ane s uc u es o he wo con igu a ions a e iden ical (i.e., hey ha e he same shape, labelling, and cha ges) and each mul ise o objec s o C is a submul ise o ha loca ed in he co esponding egion o D. The ollowing p oposi ion shows ha , while a ecognise P sys em wo king in ime migh c ea e exponen ially many objec s pe egion du ing i s compu a ion, only a polynomial amoun (wi h espec o ) o hem in each egion does ac ually play a use ul ole i he sys em is monodi ec ional: indeed, he inal esul o he compu a ion can be iden i ied by jus keeping ack o a numbe o objec s pe egion equal o he numbe o s eps ye o be ca ied ou . Lemma 1. Le Π be a monodi ec ional ecognise P sys em, and le C = ( C0,...,C ), wi h ≥ 1, be a hal ing compu a ion o Π . Then, he e exis s a sequence o con igu- a ions (D0,...,D )such ha (i) we ha e Di Ci o 0 ≤i≤ , and each mul ise o Di has a mos −i objec s; (ii) o all i< he e exis s a con igu a ion Ei+1 such ha Ei+1 is eachable in one s ep om Di(Di→ Ei+1 o b e i y) and Di+1 Ei+1; (iii) a send-ou ule o he o m [ a ] α h→ [ ] β hyes ( esp., [ a ] α h→ [ ] β hno ) is applied o he ou e mos memb ane du ing he ansi ion s ep D −1→ E i and only i Cis an accep ing ( esp., ejec ing) compu a ion. P oo . By induc ion on . I = 1, hen he en i onmen o C1 con ains yes o no , which ha e been sen ou du ing he compu a ion s ep C0→ C1 by a ule [ a ] α h→ [ ] β hyes o [ a ] α h→ [ ] β hno . Le D0 C0 be ob ained by keeping only he objec s on he le -hand side o send-ou , dissolu ion, and di ision ules applied du ing C0→ C1 (we call hese ules “blocking”, since a mos one o hem can be applied inside each memb ane a each s ep). A mos one objec pe egion is kep , gi en he lack o send-in ules. Le D1 C1 be ob ained by dele ing all objec s. Then: (i) we ha e D0 C0 and D1 C1 by cons uc ion, and all mul ise s o D0 and D1 ha e a mos 1 and exac ly 0 objec s, espec i ely; (ii) le he ansi ion D0→ E1 be compu ed by applying all blocking ules applied du ing he s ep C0→ C1 , which a e all enabled by cons uc ion; hen E1 C1 and, since D1 C1and D1con ains no objec s, necessa ily D1 E1; (iii) he compu a ion C is accep ing i and only i he ule [ a ] α h→ [ ] β hyes is applied om C0 , and he la e is equi alen by cons uc ion o ha ule being applicable om D0( he easoning is simila i Cis ejec ing). 210 A. Lepo a i e al. This p o es he base case. Now le C = ( C−1,C0,...,C ) be a hal ing compu a ion o leng h + 1. The sub-compu a ion ( C0,...,C ) is also hal ing, and by induc ion hypo hesis he e exis s a sequence o con igu a ions ( D0,...,D ) sa is ying (i)–(iii). Cons uc he con igu a ion D−1 as ollows: i s o all, keep all objec s om C−1 ha appea on he le -hand side o blocking ules applied du ing he compu a ion s ep C−1→ C0 ; his equi es a mos one objec pe egion, and gua an ees ha he memb ane s uc u e’s shape and cha ges can be upda ed co ec ly (i.e., he same as C0and D0). We mus also ensu e ha all objec s o D0 can be gene a ed om D−1 du ing he ansi ion D−1→ E0 . Once he blocking ules o be applied ha e been chosen, any objec a loca ed inside a memb ane o D0 can be aced back o a single objec in D−1 . Ei he a appea s on he igh -hand side o one o hose blocking ules, o i appea s on he igh -hand side o an objec e olu ion ule applied in he s ep C−1→ C0 , o i does no appea explici ly in any ule applied in ha s ep; in he la e case, i is ei he ca ied on unchanged om D−1 (possibly om ano he egion, i memb ane dissolu ion occu ed), o is c ea ed by duplica ing he con en o a memb ane by applying a di ision ule ( igge ed by a di e en objec ). As a consequence, a mos objec s pe egion o D−1 , possibly in conjunc ion wi h a single objec pe egion in ol ed in blocking ules, su ice in o de o gene a e he objec s pe egion o D0. As a consequence, (i) we ha e D−1 C−1 by cons uc ion, and D−1 con ains a mos + 1 objec s pe egion; (ii) by applying all blocking ules and as many e olu ion ules as possible om he compu a ion s ep C−1→ C0 in D−1 , we ob ain a con igu a ion E0 wi h he same memb ane s uc u e as D0 and, as men ioned abo e, con aining all objec s om D0(and possibly o he objec s gene a ed by e olu ion ules). Since (iii) holds by induc ion hypo hesis, his comple es he p oo . u No ice ha his lemma does no gi e us an e icien algo i hm o choosing which objec s a e impo an o each s ep o he compu a ion; i only p o es ha a small (i.e., polynomial-sized) mul ise pe egion exis s. Howe e , i is easy o ind such an algo i hm by sligh ly elaxing he condi ions: ins ead o limi ing he ca dinali y o he mul ise s o −i , we limi he numbe o occu ences o each symbol o ha alue, and simply dele e he occu ences in excess sepa a ely o each symbol. This gi es us he la ge ca dinali y bound |Γ| × ( −i ) pe egion, which is polynomial whene e he numbe o compu a ion s eps o he sys em is, and s ill allows us o simula e he o e all beha iou o he P sys em. Lemma 1 ails o P sys ems wi h send-in ules because some con igu a ions whe e each mul ise is small none heless equi e a p e ious con igu a ion wi h a egion con aining exponen ially many objec s. This is he case, o ins ance, o P sys ems sol ing coun ing p oblems, whe e he numbe o assignmen s sa is ying a Boolean o mula is checked agains a h eshold by means o send-in ules [ 4 ]. Those assignmen s a e ep esen ed in he P sys em by a po en ially exponen ial numbe o objec s loca ed in he same egion, which a e sen in o exponen ially many child en Monodi ec ional P Sys ems 211 memb anes in pa allel (i.e., a mos one objec en e s each child memb ane), and canno always be educed o a polynomial amoun wi hou changing he accep ing beha iou o he P sys em. Ano he p ope y o monodi ec ional P sys ems is he exis ence o compu a ions whe e memb anes ha ing he same labels always ha e child en (and, ecu si ely, all he descenden s) wi h he same con igu a ion. This p ope y will be use ul when simula ing con luen ecognise monodi ec ional P sys ems in Sec ion 3. Lemma 2. Le Π be a monodi ec ional P sys em. Then he e exis s a compu a- ion C = ( C0,...,C )o Π whe e, in each con igu a ion Ci , he ollowing holds: any wo subcon igu a ions 2 o Ci ha ing memb anes wi h he same label as oo s a e iden ical, excep possibly o he mul ise and cha ge o he oo memb anes hemsel es. P oo . By induc ion on i . The s a emen i ially holds o he ini ial con igu a ion o Π, since he memb anes a e injec i ely labelled. When a di ision ule is applied o a memb ane h , wo subcon igu a ions wi h oo h a e c ea ed; his is he only way o gene a e mul iple memb anes sha ing he same label. The wo esul ing subcon igu a ions may only di e wi h espec o he con en s and cha ges o he oo memb anes, since he in e nal memb anes ha e e ol ed be o e he di ision o h occu s ( ecall ha he ules a e applied, om a logical s andpoin , in a bo om-up way [8]). On he o he hand, i wo subcon igu a ions wi h iden ically labelled oo memb anes al eady exis in a con igu a ion Ci , hen we can assume ha he p ope y holds by induc ion hypo hesis. We can hen nonde e minis ically choose which ules o apply in he subcon igu a ion ha ing he i s memb ane as oo , excluding he oo i sel ; since he o he subcon igu a ion is iden ical (excep possibly o he oo ), he same mul ise o ules can also be applied o i , hus p ese ing he p ope y in he nex con igu a ion o he sys em. u While Lemma 2 somehow “comp esses” each le el o he con igu a ion o monodi ec ional P sys ems, i does no , howe e , educe he numbe o dis inc memb anes pe le el o a polynomial numbe . Indeed, he s anda d memb ane compu ing echnique o gene a ing all (exponen ially many) possible assignmen s o a se o a iables does no equi e send-in ules [ 10 ], and can be ca ied ou in pa allel on all le els o he memb ane s uc u e. Lemma 2 also ails o P sys ems wi h send-in ules. The eason is ha wo iden ical subcon igu a ions can be made di e en by ha ing a single objec loca ed immedia ely ou side, and nonde e minis ically sending i in o one o he oo memb anes o he wo sub ees; he e olu ion o he wo b anches o he sys em migh hen di e ge comple ely. 2 We de ine a subcon igu a ion o Ci as a sub ee (a oo node oge he wi h all i s descenden s) o he memb ane s uc u e o Ci , including labels, mul ise s, and cha ges o he memb anes. 212 A. Lepo a i e al. 3 Simula ion o monodi ec ional P sys ems I is a well-known esul in memb ane compu ing ha P sys ems wi h ac i e memb anes can be simula ed in polynomial ime by de e minis ic Tu ing machines i no memb ane di ision ules a e allowed [ 10 ]. Mo e speci ically, he po ion o he sys em ha is no subjec o memb ane di ision can be simula ed de e minis ically wi h a polynomial slowdown, while he ou pu o he di iding memb anes can be ob ained by que ying an app op ia e o acle. I was ecen ly p o ed ha , o s anda d (bidi ec ional) P sys ems whe e only elemen a y memb anes can di ide, an o acle o a #P unc ion is necessa y and su icien [5]. In wha ollows we p o e ha an NP -o acle is su icien o he simula ion o monodi ec ional P sys ems. In pa icula , he o acle will sol e he ollowing p oblem. Lemma 3. Gi en he ini ial con igu a ion o an elemen a y memb ane wi h label h o a monodi ec ional P sys em, an objec ype a∈Γ , and wo in ege s k, ∈N in una y no a ion, i is NP -comple e o decide whe he he se o memb anes wi h label h exis ing a ime emi s ( ia send-ou o dissolu ion ules) a leas k copies o objec aa ha ime s ep. P oo . The p oblem is NP -ha d, since one can simula e an a bi a y polynomial- ime, nonde e minis ic Tu ing machine M by using a single memb ane wi h ele- men a y di ision (wi hou using send-in ules) and ob ain he same esul as M by checking i he esul ing memb anes send ou a leas one ( k = 1) “accep ance objec ” a a speci ic ime s ep [4]. Con e sely, he p oblem can be sol ed by a nonde e minis ic, polynomial- ime Tu ing machine M as ollows. Simula e compu a ion s eps o he memb ane explic- i ly, by keeping ack o i s cha ge and mul ise , as in any s anda d simula ion [ 10 ]. I he memb ane di ides, hen M keeps ack o all he esul ing memb anes, un il he numbe exceeds k . I ha happens, hen k copies o he memb ane a e chosen nonde e minis ically among hose being simula ed (which a e a mos 2 k a e any simula ed s ep, i all memb anes di ide), and he emaining ones a e disca ded. Since he e is no incoming communica ion, any ins ance o he memb ane can be simula ed co ec ly, as i s beha iou does no depend on he beha iou o i s siblings. I one o he simula ed memb anes dissol es be o e s eps, one o he k “slo s” is eleased and can be eused in case o a u he memb ane di ision. A e ha ing simula ed s eps as desc ibed, he machine M accep s i and only i a leas k copies o a a e emi ed (sen ou , o eleased by dissolu ion) in he las s ep by he memb anes being simula ed. A mos k memb anes need o be simula ed in o de o check whe he a leas k copies o he objec a e emi ed and, by exploi ing nonde e minism, we a e gua an eed ha he co ec subse o memb anes is chosen by a leas one compu a ion o M . Since k and a e polynomial wi h espec o he size o he inpu , he esul ollows. u Monodi ec ional P Sys ems 213 The alues o and k a e gi en in una y since, o he wise, he numbe o s eps o he numbe o memb anes o simula e could be exponen ial wi h espec o he size o he inpu , and he p oblem would no be sol able in polynomial ime. As a consequence o Lemma 3, monodi ec ional P sys ems wi hou non- elemen a y di ision can be simula ed in polynomial ime wi h access o an NP o acle. Theo em 1. PMC? M(−wn) ⊆PNP. P oo . The ules applied o non-elemen a y memb anes can be simula ed di ec ly in de e minis ic polynomial ime by a Tu ing machine M [ 5 ]; his includes he ou e mos memb ane, which ul ima ely sends ou he esul objec . In o de o upda e he con igu a ions o he non-elemen a y memb anes co ec ly, he objec s emi ed om elemen a y memb anes (which po en ially di ide) ha e o be added o hei mul ise s. Suppose he P sys ems o he amily being simula ed wo k in polynomial ime p ( n ). By Lemma 1, he inal esul o he compu a ion can be co ec ly de e mined by keeping ack o a mos p ( n ) copies o each objec pe egion. Hence, we can upda e he con igu a ions by using an o acle o he p oblem o Lemma 3. A ime s ep , we make mul iple que ies o each label h o an elemen a y memb ane and o each objec ype a∈Γ : by pe o ming a bina y sea ch on k o e he ange [0 , p ( n )], we can ind he exac numbe o copies o a emi ed by memb anes wi h label h a ime , o disco e ha his numbe is a leas p ( n ) (and, in ha case, we only add p ( n ) objec s o he mul ise ). This comple es he p oo . u Monodi ec ional P sys ems wi hou non-elemen a y di ision become weake i dissolu ion is also disallowed: now a memb ane canno become elemen a y du ing he compu a ion, and hus he e olu ion o each di iding memb ane is always independen o he es o he sys em. This allows us o pe o m all que ies in pa allel, a he han sequen ially (in an adap i e way). Theo em 2. PMC? M(−d,−wn) ⊆PNP k. P oo . I dissolu ion ules a e no allowed, being elemen a y is a s a ic p ope y o he memb anes, i.e., a memb ane is elemen a y o he whole compu a ion i and only i i is elemen a y in he ini ial con igu a ion. By obse ing ha each que y is comple ely independen o he o he s (i.e., each que y in ol es a di e en memb ane, ime s ep and objec ) and also independen o he con igu a ions o he non-di iding memb anes (due o he lack o send-in ules), we can pe o m hem in pa allel e en be o e s a ing o simula e he P sys em. This p o es he inclusion in PNP k.u Now conside monodi ec ional P sys ems wi h non-elemen a y memb ane di i- sion. Fo his kind o sys ems, he beha iou o a di iding memb ane is, o cou se, dependen on he beha iou o i s child en and, ecu si ely, o all i s descendan s. 214 A. Lepo a i e al. In o de o simula e he beha iou o he child en by using o acles, we de ine a mo e gene al que y p oblem, whe e we assume ha he beha iou o he descenden s o he memb ane men ioned in he que y has al eady been es ablished. Fi s o all, no ice ha he lack o send-in ules allows us o ex end he no ion o ansi ion s ep C → D be ween con igu a ions o labelled sub o es s 3E o C and F o D as E → F ; he only di e ences om he s anda d de ini ion a e ha E is no necessa ily a single ee, and ha i s ou e mos memb anes may di ide and dissol e. De ini ion 2. Le Π be a monodi ec ional P sys em, le C be a con igu a ion o Π , and le h∈Λ be a memb ane label. A sub o es S o C is called a label-sub o es induced by h, o h-sub o es o b e i y, i one o he ollowing condi ions hold: • C is he ini ial con igu a ion o Π , and S consis s o a single ee oo ed in he (unique) memb ane h, • C is a possible con igu a ion o Π a ime + 1 wi h C0→ C , and he e exis s an h-sub o es S0in C0such ha S0→ S. The no ion o h -sub o es can be iewed as a gene alisa ion o he equi alence classes o memb anes in P sys ems wi hou cha ges de ined by Mu phy and Woods [6]. Lemma 4. Le Π be a monodi ec ional P sys em. Then he e exis s a compu a ion o Π whe e, a each ime s ep and o each memb ane label h∈Λ , all h -sub o es s a e iden ical. P oo . Mul iple h -sub o es s can only be c ea ed by di ision o an ances o o h ; bu hen, by Lemma 2, he e exis s a compu a ion o Π whe e he esul ing h -sub o es s a e iden ical. u Example 1. Figu e 1 shows he e olu ion o he memb ane s uc u e o a monodi- ec ional P sys em and i s label-sub o es s. The label-sub o es s in he ini ial con igu a ion C0 coincide wi h all downwa d-closed sub ees. In he compu a ion s ep C0→ C1 bo h h2 and h3 di ide; he di ision o he la e causes he duplica ion o he h3 - and h4 -sub o es s (and, indi ec ly, o he h5 -sub o es ); he di ision o an ances o memb ane is he only way o ha e mo e han one label-sub o es . By Lemma 4, we can always assume ha mul iple label-sub o es s induced by he same label a e iden ical. In he compu a ion s ep C1→ C2 , he igh mos memb ane ha ing label h2 and bo h ins ances o h4 dissol e. No ice ha his does no cause he disappea ance o he wo h4 -sub o es s: in he gene al case, he memb anes h4 migh con ain label-sub o es s induced by di e en labels, and we s ill need o e e o hem as a single en i y ( he h4 -sub o es ), wi hou he need o desc ibe he in e nal s uc u e, e en when h4ceases o exis . As can be obse ed om Figu e 1, a sub o es can be iden i ied as an h -sub o es by checking whe he i can be gene a ed om he downwa d-closed sub ee oo ed in hin he ini ial con igu a ion. 3 We de ine a sub o es F0 o a o es F o be any subg aph such ha , whene e F0 includes a e ex , i also includes all he descenden s o . Monodi ec ional P Sys ems 215 h1 h2 h4 h5 h2 h4 h5 h1 h2 h3 h4 h5 h3 h3h3 h3 h1 h2 h3 h3h3 h3 h4 h5 h4 h5 C0C1 C2 Fig. 1. E olu ion o a memb ane s uc u e and i s label-sub o es s, which a e enclosed by dashed ec angles. A compu a ion ha ensu es ha all h -sub o es s a e iden ical o all h∈Λ can be ob ained by imposing a o al o de ing (a p io i y) on he se o ules o he P sys em, and applying inside each memb ane he ules wi h highe p io i y whene e possible. In he ollowing, we assume ha a p io i y o de (e.g., he lexicog aphic o de ) has been ixed; he e is no loss o gene ali y in doing ha , since we only ocus on con luen P sys ems in his pape . We de ine he mul ise o objec s emi ed by a label-sub o es as he union o he mul ise s emi ed by i s ou e mos memb anes. Lemma 5. Gi en he ini ial con igu a ion o a memb ane wi h label h o a monodi- ec ional P sys em, an objec a∈Γ , wo in ege s k, ∈N in una y no a ion, and a able T o he objec s emi ed du ing compu a ion s eps 1 , . . . , by he label-sub o es s immedia ely con ained in h , i is NP -comple e o decide whe he each h -sub o es emi s a leas kcopies o objec aa ime . 222 A. Lepo a i e al. Theo em 4. A de e minis ic polynomial- ime Tu ing machine which asks p ( n ) que ies o an NP o acle on inpu s o leng h n can be simula ed by a uni o m amily o monodi ec ional P sys ems o dep h p ( n )wi hou non-elemen a y di ision ules. P oo . The amily o P sys ems Π = {Πx : x∈ { 0 , 1 }?} simula ing M on inpu x can be cons uc ed uni o mly in polynomial ime, since only he ini ial mul ise depends on he ac ual s ing x , while he se o ules and he memb ane s uc u e only depend on |x| . We only need o make su e ha he indices o he ape-objec s a e la ge enough o ensu e ha bo h he ape o M and he ape o M0 can be ep esen ed a he same ime. u Co olla y 1. PNP ⊆PMCM(−wn).u Ins ead o using memb ane dissolu ion as in ule (23) , we can use he objec ˆq0 ! o p oduce ⊕: [ˆq0 !→ ⊕]α h o α∈ {+,−} (26) which ensu es ha he cha ge o h is posi i e ins ead o nega i e wo s eps la e . The ape-objec s a e hen sen ou , one a a ime, by using he ollowing ules: [1i]+ h→[ ]+ h1i o −(m−1) ≤i≤m−1 (27) The ime o he objec ˜q!, has o be inc eased app op ia ely, in o de o ake in o accoun he ime needed o send ou all he ape-objec s. Howe e , since he memb ane whe e he simula ion o M is non-elemen a y a e he i s que y, ule (20) is now a weak non-elemen a y di ision ule. As a consequence, we ha e: Theo em 5. A de e minis ic polynomial- ime Tu ing machine which asks p ( n ) que ies o an NP o acle on inpu s o leng h n can be simula ed by a uni o m amily o monodi ec ional P sys ems o dep h p(n)wi hou dissolu ion ules. u Co olla y 2. PNP ⊆PMCM(−d).u In o de o p o e he con e se o Theo em 2, we in oduce an auxilia y com- plexi y class (a a ian o he class o op imisa ion p oblems Op P [3]). De ini ion 3. De ine O P o be he class o unc ions :{ 0 , 1 }?→ { 0 , 1 }? ha ing a polynomial- ime nonde e minis ic Tu ing machine M such ha , o all x∈ { 0 , 1 }? , we ha e ( x ) = WM ( x ), whe e M ( x )deno es he se o possible ou pu s ings o M on inpu x , and W deno es bi wise disjunc ion o s ings; he e we assume ha he bi wise disjunc ion o s ings o di e en leng hs is pe o med by padding he sho es ones wi h ze os. The pu pose o he class O P is o cap u e a polynomial numbe o pa allel NP que ies wi h a single que y o a unc ion o e bina y s ings. P oposi ion 1. PNP k=PO P[1]. Monodi ec ional P Sys ems 223 P oo . A polynomial numbe o pa allel que ies y1, . . . , ym o an o acle o L∈NP can be eplaced by a single que y o an o acle o he unc ion ( y1, . . . , ym ) = z1· · · zm , whe e zi = 1 i and only i yi∈L . Le M be an NP machine decid- ing L , and le M0 be he ollowing nonde e minis ic machine: on inpu y1, . . . , ym simula e M on each yi and eco d he co esponding ou pu bi zi ; inally, ou - pu z1· · · zm . Fo all 1 ≤i≤m , i yi is accep ed by he o acle, hen he e exis s a compu a ion o M0 such ha zi = 1: hus, by aking he bi wise disjunc ion o all possible ou pu s ings o M0 , we ob ain he i - h bi o ( y1, . . . , ym ); his p o es ha ∈O P . No ice ha his p oo equi es he que y s ings y1, . . . , ym o be ixed in ad ance, i.e., he que ies canno be pe o med adap i ely. Vice e sa, a single que y o an o acle o ∈O P wi h que y s ing y can be eplaced by he ollowing polynomial numbe o pa allel que ies, one o each 1 ≤i≤ | ( y ) | : “is he i - h bi o ( y ) a 1?”. These que ies a e in NP , since hey can be answe ed by simula ing an O P machine M o and selec ing only i s i - h ou pu bi ; he answe will be posi i e i and only i he e exis s a compu a ion o M ha ing a 1 as he i - h ou pu bi , which (by de ini ion o O P ) is equi alen o he i- h bi o (y) being 1. u Simula ing an O P que y by means o a P sys em is comple ely analogous o simula ing an NP que y, excep ha , ins ead o a single ou pu bi , we ha e a polynomial numbe o hem. These bina y s ings a e au oma ically combined by bi wise disjunc ion when he ape-objec s a e sen ou o he memb ane simula ing he nonde e minis ic Tu ing machine. Fu he mo e, since a single O P que y su ices o cap u e PNP k, we ob ain he ollowing esul s: Theo em 6. A de e minis ic polynomial- ime Tu ing machine which asks a poly- nomial numbe o pa allel que ies o an NP o acle on inpu s o leng h n can be simula ed by a uni o m amily o monodi ec ional P sys ems o dep h 1 wi hou dissolu ion (and, necessa ily, wi hou non-elemen a y di ision). u Co olla y 3. PNP k⊆PMCM(−d,−wn).u 5 Fu he esul s The dep h o he P sys ems o Theo ems 4 and 5 can be asymp o ically educed by exploi ing he equi alence o a loga i hmic numbe o adap i e que ies and a polynomial numbe o pa allel que ies [ 7 , Theo em 17.7], o mally PNP k = PNP[log n] . Suppose a de e minis ic polynomial- ime Tu ing machine pe o ms p ( n ) sequen ial NP que ies, and di ide hese que ies in o Θ ( p ( n ) /log n ) blocks o Θ ( log n ) que ies. Each block can hen be eplaced by a polynomial numbe o pa allel NP que ies o , by P oposi ion 1, by a single O P que y. Hence, p ( n ) sequen ial NP que ies can be simula ed by Θ ( p ( n ) /log n ) sequen ial O P que ies, and each o he la e can be simula ed by one le el o dep h in a P sys em: 224 A. Lepo a i e al. Co olla y 4. A de e minis ic polynomial- ime Tu ing machine which asks p ( n ) que ies o an NP o acle on inpu s o leng h n can be simula ed by a uni o m amily o monodi ec ional P sys ems o dep h Θ ( p ( n ) /log n )wi hou non-elemen a y di ision ules ( esp., wi hou di ision ules). u Theo em 3 can be sha pened by making he in a-le el que y pa allelism explici wi h O P que ies: Co olla y 5. Le Π be a amily o semi-uni o m polynomial- ime monodi ec ional P sys ems o dep h ( n ). Then Π can be simula ed by a polynomial- ime de e min- is ic Tu ing machine wi h (n)que ies o an O P o acle. u We can also p o e ha monodi ec ional amilies o P sys ems o any con- s an dep h, e en wi h dissolu ion and non-elemen a y di ision ules (in sym- bols M(O(1)) ), a e always equi alen o amilies o dep h one wi hou dissolu ion and wi hou non-elemen a y di ision (in symbols M(1,−d,−wn) ), and hus only able o simula e pa allel NP que ies. Theo em 7. PMC[?] M(O(1)) =PMC[?] M(1,−d,−wn) =PNP k. P oo . By Theo em 6, we al eady know ha PNP k⊆PMCM(O(1)) , e en when limi ed o dep h 1; he inclusion PMCM(O(1)) ⊆PMC? M(O(1)) holds by de ini ion. The inclusion PMC? M(O(1)) ⊆PNP k can be p o ed as ollows. By Theo em 3, a amily o P sys ems o cons an dep h k can be simula ed in polynomial ime by asking k se s (one pe le el) o p ( n ) pa allel que ies, o some polynomial p . Each se o p ( n ) pa allel que ies can be con e ed in o Θ ( log n ) sequen ial que ies [ 7 , Theo em 17.7], o a o al o k×Θ ( log n ) sequen ial que ies. These can be con e ed back in o a polynomial numbe o pa allel que ies. u Finally, obse e ha Theo em 3 also i ially holds o monodi ec ional P sys- ems wi hou cha ges. This implies a be e uppe bound han p e iously known [ 5 ] o a monodi ec ional a ian o he P conjec u e [ 9 , P oblem F], which s a es ha P sys ems wi hou cha ges and wi hou non-elemen a y di ision cha ac e ise P. 6 Conclusions In his pape we con i med he impo ance o he di ec ion o he in o ma ion low in P sys ems wi h ac i e memb anes wi h espec o hei compu ing powe . Indeed, when wo king in polynomial ime and using only ou wa d-bound communica ion, he co esponding complexi y class dec eases om PSPACE o PNP , o om P#P o PNP k when non-elemen a y di ision and dissolu ion ules a e disallowed. I is in e es ing o no ice ha , unlike wi h o he es ic ions such as emo ing memb ane di ision [ 10 ] o cha ges and dissolu ion [ 2 ], he esul ing P sys ems a e s ill mo e powe ul han P(unless, o cou se, P=NP). Monodi ec ional P Sys ems 225 The ole o s ong non-elemen a y di ision (which is eplaced in his pape by weak non-elemen a y di ision) in he absence o send-in ules is s ill unclea . E en i i p o ides a way o con ey in o ma ion om a pa en memb ane o i s child en, we do no know whe he his is su icien o al oge he eplace send-in communica ion while main aining a polynomial un- ime. Finally, i would be in e es ing o in es iga e monodi ec ional P sys ems whe e he in o ma ion low is e e sed, i.e., send-ou communica ion and dissolu ion ules (as well as s ong non-elemen a y di ision ules) a e disallowed. A i s issue o o e come is choosing an app op ia e accep ance condi ion o he P sys ems, o eplace sending ou yes o no om he ou e mos memb ane. The accep ance condi ion mos simila “in spi i ” o he o iginal one is p obably accep ing ( esp., ejec ing) by ha ing a leas one yes ( esp., no ) objec appea , ei he anywhe e in he sys em, o inside a dis inguished (and possibly di iding) memb ane, du ing he las compu a ion s ep; we also add he es ic ion ha yes and no can ne e appea oge he , since gi ing he p io i y o one o hem would allow us o sol e NP - comple e (o coNP -comple e) p oblems “ o ee”. Such monodi ec ional P sys ems appea o be e y weak when wo king in polynomial ime; indeed, e en hough exponen ially many memb anes can s ill be c ea ed by di ision, hey can ne e communica e. Is P ac ually an uppe bound o he class o p oblems hey can sol e? Re e ences 1. Alhazo , A., Ma ´ın-Vide, C., Pan, L.: Sol ing a PSPACE-comple e p oblem by ecognizing P sys ems wi h es ic ed ac i e memb anes. Fundamen a In o ma icae 58(2), 67–77 (2003) 2. Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J., Riscos-Nu˜nez, A., Rome o-Campe o, F.J.: Compu a ional e iciency o dissolu ion ules in memb ane sys ems. In e na ional Jou nal o Compu e Ma hema ics 83(7), 593–611 (2006) 3. K en el, M.W.: The complexi y o op imiza ion p oblems. Jou nal o Compu e and Sys em Sciences 36, 490–509 (1988) 4. Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A.E., Zand on, C.: Memb ane di ision, o acles, and he coun ing hie a chy. Fundamen a In o ma icae (2015), in p ess 5. Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A.E., Zand on, C.: Simula ing elemen- a y ac i e memb anes, wi h an applica ion o he P conjec u e. In: Gheo ghe, M., Rozenbe g, G., Sos´ık, P., Zand on, C. (eds.) Memb ane Compu ing, 15 h In e na ional Con e ence, CMC 2014, Lec u e No es in Compu e Science, ol. 8961, pp. 284–299. Sp inge (2015) 6. Mu phy, N., Woods, D.: Ac i e memb ane sys ems wi hou cha ges and using only symme ic elemen a y di ision cha ac e ise P. In: Ele he akis, G., Ke alas, P., P˘aun, Gh., Rozenbe g, G., Salomaa, A. (eds.) Memb ane Compu ing, 8 h In e na ional Wo kshop, WMC 2007. Lec u e No es in Compu e Science, ol. 4860, pp. 367–384 (2007) 7. Papadimi iou, C.H.: Compu a ional Complexi y. Addison-Wesley (1993) 8. P˘aun, Gh.: P sys ems wi h ac i e memb anes: A acking NP-comple e p oblems. Jou nal o Au oma a, Languages and Combina o ics 6(1), 75–90 (2001) 226 A. Lepo a i e al. 9. P˘aun, Gh.: Fu he wen y six open p oblems in memb ane compu ing. In: Gu ´ıe ez- Na anjo, M.A., Riscos-Nu˜nez, A., Rome o-Campe o, F.J., Sbu lan, D. (eds.) P oceed- ings o he Thi d B ains o ming Week on Memb ane Compu ing. pp. 249–262. F´enix Edi o a (2005) 10. Zand on, C., Fe e i, C., Mau i, G.: Sol ing NP-comple e p oblems using P sys ems wi h ac i e memb anes. In: An oniou, I., Calude, C.S., Dinneen, M.J. (eds.) Uncon- en ional Models o Compu a ion, UMC’2K, P oceedings o he Second In e na ional Con e ence, pp. 289–301. Sp inge (2001) 11. Zand on, C., Lepo a i, A., Fe e i, C., Mau i, G., P´e ez-Jim´enez, M.J.: On he compu a ional e iciency o pola iza ionless ecognize P sys ems wi h s ong di ision and dissolu ion. Fundamen a In o ma icae 87, 79–91 (2008)