P systems with input in binary form

P SYSTEMS WITH INPUT IN BINARY FORM ALBERTO LEPORATI∗ CLAUDIO ZANDRON† Dipa imen o di In o ma ica, Sis emis ica e Comunicazione Uni e si `a degli S udi di Milano – Bicocca Via Bicocca degli A cimboldi 8, 20126 Milano, I aly and MIGUEL A. GUTI´ ERREZ-NARANJO‡ Resea ch G oup on Na u al Compu ing Depa men o Compu e Science and A i icial In elligence Se illa Uni e si y A da Reina Me cedes s/n, 41012 Se illa, Spain Recei ed ( ecei ed da e) Re ised ( e ised da e) Communica ed by Edi o ’s name ABSTRACT Cu en P sys ems which sol e NP–comple e nume ical p oblems ep esen ins ances in una y no a ion. In classical complexi y heo y, based upon Tu ing machines, swi ching om bina y o una y encoded ins ances gene ally co esponds o simpli y he p oblem. In his pape we show ha his does no occu when wo king wi h P sys ems. Namely, we p opose a simple me hod o encode bina y numbe s using mul ise s, and a amily o P sys ems which ans o ms such mul ise s in o he usual una y no a ion.a Keywo ds: Memb ane Compu ing; P sys ems; Bina y da a; Pa i ion 1. In oduc ion P sys ems (also called memb ane sys ems) we e in oduced in [?] as a new class o dis ibu ed and pa allel compu ing de ices, inspi ed by he s uc u e and unc ion- ing o li ing cells. The basic model consis s o a hie a chical s uc u e composed by se e al memb anes, embedded in o a main memb ane called he skin. Memb anes di ide he Euclidean space in o egions, ha con ain some objec s ( ep esen ed by symbols o an alphabe ) and e olu ion ules. Using hese ules, he objec s may e ol e and/o mo e om a egion o a neighbo ing one. The ules a e applied in a nonde e minis ic and maximally pa allel way: all he objec s ha may e ol e a e ∗lep[email p o ec ed] . †[email p o ec ed]. ‡[email p o ec ed] 1 o ced o e ol e. A compu a ion s a s om an ini ial con igu a ion o he sys em and e mina es when no e olu ion ule can be applied. The esul o a compu a ion is he mul ise o objec s con ained in o an ou pu memb ane o emi ed o he en i onmen om he skin o he sys em. In wha ollows we assume he eade is al eady amilia wi h he basic no ions and he e minology unde lying P sys emsb. Many P sys ems which sol e NP–comple e decision p oblems ha e appea ed in he li e a u e du ing he las ew yea s. Bo h in he ield o nume ical p oblems, ha is, p oblems whose ins ances consis o se s o sequences o in ege numbe s (see o example Subse Sum [?], Knapsack [?], Bin Packing [?] o Pa i ion [?] p oblems) o non-nume ical p oblems as SAT [?,?] o QSAT [?]. I is well known [?,?] ha he di icul y o such nume ical p oblems is ied o he magni ude o he numbe s which appea in o he ins ance. Fo example, le us conside he Pa i ion p oblem, which can be s a ed as ollows: P oblem 1.1 Name:Pa i ion. •Ins ance: a se A={a1, a2,...,an}o posi i e in ege numbe s •Ques ion: is he e a subse A′⊆Asuch ha P a′∈A′ a′=P a∈A A′ a? The ollowing algo i hm sol es he p oblem using he well known Dynamic P og am- ming echnique [?]. In pa icula , he algo i hm e u ns 1 on posi i e ins ances, and 0 on nega i e ins ances. Pa i ion({a1, a2,...,an}) s←Pn i=1 ai i smod 2 = 1 hen e u n 0 o j←1 o s/2 do M[1, j]←0 M[1,0] ←M[1, a1]←1 o i←2 o n do o j←0 o s/2 do M[i, j]←M[i−1, j] i j≥aiand M[i−1, j −ai]> M[i, j] hen M[i, j]←M[i−1, j −ai] e u n M[n, s/2] Fi s o all, he algo i hm compu es he sum so all elemen s in he ins ance. I s is odd hen he ins ance is ce ainly nega i e, and hus he algo i hm e u ns 0. I sis e en hen he algo i hm checks o he exis ence o a subse A′⊆Asuch ha Pa′∈A′a′=s 2. In o de o look o A′, he algo i hm uses a n×(s 2+ 1) ma ix Mwhose en ies a e om {0,1}. I ills he ma ix by ows, s a ing om he i s ow. Each ow is illed om le o igh . The en y M[i, j] is illed wi h 1 i and bA layman-o ien ed in oduc ion can be ound in [?]; a o mal desc ip ion in [?] and he la es in o ma ion abou P sys ems can be ound on [?]. 2 only i he e exis s a subse o {a1, a2,...,ai}whose elemen s sum up o j. The gi en ins ance o Pa i ion is hus a posi i e ins ance i and only i M[n, s 2] = 1 a he end o he execu ion. Since each en y is conside ed exac ly once o de e mine i s alue, he ime complexi y o he algo i hm is p opo ional o n(s 2+ 1) = Θ(ns). This means ha he di icul y o he p oblem depends on he alue o s, ha is, on he magni ude o he alues in A. In ac , le us deno e by K he maximum elemen o A. I Kis polynomially bounded w. . . n hen also s=Pn i=1 ai≤Kn is polynomially bounded w. . . n, and hus he abo e algo i hm wo ks in polynomial ime. On he o he hand, i Kis exponen ial w. . . n, say K= 2n, hen also sis exponen ial and he abo e algo i hm wo ks in exponen ial ime and space. This beha io is usually e e ed o in he li e a u e by elling ha he Pa i ion p oblem is a pseudo–polynomial NP–comple e p oblem. The ac ha in gene al he abo e algo i hm is no a polynomial ime algo i hm o Pa i ion can be immedia ely unde s ood by compa ing i s ime complexi y wi h he ins ance size. The usual size o he ins ances o Pa i ion is Θ(nlog K) (also O(nlog s) in [?, page 91]), since o conciseness e e y “ easonable” encoding is assumed o ep esen each elemen o Ausing a s ing whose leng h is O(log K). He e all loga i hms a e aken wi h base 2. S a ed di e en ly, he size o he ins ance is usually conside ed o be he numbe o bi s which mus be used o ep esen in bina y all he in ege numbe s which occu in A. I we would ep esen such numbe s using he una y no a ion, hen he size o he ins ance would be Θ(nK). Bu in his case we could w i e a p og am which i s con e s he ins ance in bina y o m and hen uses he abo e algo i hm o sol e he p oblem in polynomial ime wi h espec o he new ins ance size. We can hus conclude ha he di icul y o a nume ical NP–comple e p oblem depends also on he measu e o he ins ance size we adop . The ac ha he di icul y o a p oblem gene ally depends upon how we measu e he ins ance size is e en mo e appa en i we conside he Fac o iza ion p oblem: P oblem 1.2 Name:Fac o iza ion. •Ins ance: a posi i e in ege numbe nwhich is he p oduc o wo p ime numbe s pand q •Ou pu :p This p oblem is gene ally conside ed in ac able, which means ha no polynomial ime algo i hm is known ha sol es i on e e y ins ance. The conjec u ed in- ac abili y o his p oblem is o en exploi ed in C yp og aphy: a no able example is he RSA c yp osys em [?]. He e he na u al ins ance size o he p oblem is Θ(log n), he numbe o bi s which a e needed o ep esen nin bina y o m. Also o his p oblem, i we le he ins ance size be Θ(n) hen he i ial algo i hm which ies o di ide nby e e y numbe comp ised be ween 1 and √nis a polynomial ime algo i hm which sol es he Fac o iza ion p oblem. Fo hese easons we belie e ha i is impo an o show ha P sys ems which sol e NP–comple e nume ical p oblems do no ake hei powe om he ac ha he ins ances a e ep esen ed in una y no a ion. Hence in his pape we i s p opose 3 a simple me hod o ep esen posi i e in ege numbe s in bina y no a ion using mul ise s o objec s. Then, we p opose a amily o P sys ems which ans o ms his bina y encoding in o he una y no a ion used in [?,?,?,?]. The pape is o ganized as ollows. In sec ion 2 we in oduce ou encoding o bina y numbe s using mul ise s. In sec ion 3 we p opose a amily o simple P sys ems which can be used o ans o m a gi en posi i e in ege numbe om such encoding o una y no a ion. Sec ion 4 concludes he pape and gi es some di ec ions o u u e esea ch. 2. Encoding bina y numbe s using mul ise s Fi s o all le us show how a gi en posi i e in ege numbe xcan be ep esen ed in bina y no a ion using a mul ise . Le xn, xn−1,...,x1be he bina y ep esen a- ion o x, so ha x=Pn i=1 xi2i−1. We use he objec s om he ollowing alphabe : An={hb, ji|b∈ {0,1}, j ∈ {1,2,...,n}} (1) Objec hb, jiis used o ep esen bi bin o posi ion jin he bina y encoding o an in ege numbe . Hence, o ep esen he abo e numbe xwe will use he ollowing mul ise (ac ually, a se ) o objec s: hxn, ni,hxn−1, n −1i,...,hx1,1i Le us ema k ha he alphabe Adepends on he leng h o he bina y ep e- sen a ion o he numbe x, i.e., wi h he alphabe Anwe can ep esen om 1 o 2n−1. On he o he hand, he una y ep esen a ion o xis ob ained by choosing a symbol om an alphabe , say he symbol a om alphabe A′, and pu ing in o he mul ise xcopies o such symbol: ax. Hence, una y no a ion is exponen ially longe han bina y no a ion. Ou ans o ma ion hus sol es ano he p oblem aised by he solu ions exposed in [?,?,?,?]: in o de o p o ide he inpu alues o he P sys ems, we should inse in o such sys ems an exponen ial (wi h espec o he ins ance size) numbe o objec s. This means ha an exponen ial amoun o wo k o p epa e he sys em is equi ed. Wo king wi h bina y encoded numbe s, ins ead, allows one o p epa e he sys em by inse ing a polynomially bounded numbe o objec s. 3. Con e ing om bina y o una y no a ion In his sec ion we p opose a amily o simple P sys ems which allows o con e a gi en posi i e in ege numbe x, exp essed in bina y no a ion as exposed in he p e ious sec ion, o he usual una y no a ion. The objec s used by he P sys ems o m a subse o alphabe Ao equa ion (??). Namely, in o de o ep esen xin bina y no a ion we will use only he objec s which co espond o he bi s o xwhich a e equal o 1. Fo example, i x= 25 hen i s bina y ep esen a ion is 11001, and we will use he objec s h1,5i,h1,4i, and h1,1i o ep esen i . Since he i s elemen in he pai s o Aused is always equal o 1, 4 we can be mo e concise by omi ing i . Once omi ed he i s elemen o he pai , also angula pa en hesis a e supe lous. The amily o P sys ems which pe o ms he ans o ma ion is o mally de ined as ollows: Π(n) = (A(n), µ, w, R(n), iin, iou ) whe e: •A(n) = {1,2,...,n}∪{a}is he alphabe ; •µ= [ ]skin is he memb ane s uc u e consis ing o he skin only; •w=∅is he mul ise o objec s ini ially p esen in egion 1; •R(n) is he ollowing se o e olu ion ules associa ed wi h egion 1: [j→(j−1)2]skin o all j∈ {2,3,...,n} [1 →a]skin •iin =skin speci ies he inpu memb ane o Π; •iou =skin speci ies he ou pu memb ane o Π. The seman ics o he ules is he usual o e olu ion ules. All hey a e applied in a maximal pa allel mode. The numbe o cellula s eps o he P sys em is bounded by nand he compu a ion hal s when no mo e ules can be applied. When his happens, he mul ise placed in he ou pu memb ane ( he only one memb ane) is he ou pu o he compu a ion. Compu a ions p oceed as ollows. The objec s which deno e he posi ions o 1’s in he bina y ep esen a ion o xa e ini ially pu in o he egion enclosed by he skin. Then he compu a ion s a s, and he ules om Ra e applied. I is easily seen ha he p esence o objec j, wi h j∈ {1,2,...,n}, will p oduce 2j−1copies o objec a. Hence a he end o he compu a ion, when no mo e ules om Rcan be applied, he skin will con ain xcopies o objec a, ha is, he una y ep esen a ion o x. We conclude his sec ion wi h an example o compu a ion o he abo e P sys ems. Le us conside again he alue x= 25; as p e iously said, i will be ep esen ed by means o objec s 5, 4, and 1 (each in a unique copy). A he i s s ep o compu a ion, we apply in pa allel he ules 1 →a, 4 →3,3 and 5 →4,4, ob aining he mul ise a, 3,3,4,4. Then, we apply in pa allel he ule 3 →2,2 on each copy o he symbol 3, hus ob aining ou copies o he symbol 2, and he ule 4 →3,3 on each copy o he symbol 4, hus ob aining ou copies o he symbol 3. The mul ise we ob ain a e he second s ep o compu a ion will be a, 2,2,2,2,3,3,3,3. Hence, we apply he ules 2 →1,1 and 3 →2,2 ob aining a, 18,28. By means o he ules 1 →aand 2 →1,1 we hen ob ain he mul ise a9,116 and inally, applying again 1 →awe ob ain he mul ise a25 which is exac ly he una y codi ica ion o he ini ially bina y coded numbe . 5 F om he p e ious de ini ion and example, i is easy o see ha he ca dinali y o he alphabe and he numbe o compu a ion s eps a e linea wi h espec o he inpu size. 4. Composi ion o P sys ems In he p e ious sec ion, a me hod o con e ing na u al numbe om bina y in o una y no a ion has been desc ibed. In ui i ely, such a P sys em could be composed wi h a P sys em which sol es an ins ance o a p oblem wi h inpu in una y o m and o ge a new P sys em which sol es he same p oblem wi h inpu in bina y o m. The o maliza ion o such in ui ion has se e al echnical de ails and, o he bes o ou knowledge, he composi ion o P sys ems has no been de ined. In his sec ion we p esen a de ini ion o composing P sys ems which i in o ou pu poses. The gene al de ini ion and he s udy o i s p ope ies lies ou o he scope o his pape . Fi s we de ine a join o wo P sys ems Ajoin P1◦P2o P sys ems P1and P2is a new P sys em whe e he skin memb ane o P2is iden i ied o an elemen a y memb ane o P1. In his way we ob ain a new labelled memb ane s uc u e. Each labelled memb ane keeps i s ini ial mul ise and se o ules. In he ini ial con igu a ion, he new memb ane ob ained by iden i ica ion, he ini ial mul ise and se o ules a e he union o he mul ise s and se s o ules o he iden i ied memb anes. Nex we gi e a o mal de ini ion. De ini ion 1 Le P1= (O1, H1, EC1, µ1, w1 1,...,w1 m1, R1)and P2= (O2, H2, EC2, µ2, w2 1, . . . , w2 m2, R2)be wo P sys ems whe e: m1, m2≥1a e he ini ial deg ees o he sys ems; O1and O2a e he alphabe s o objec s; H1and H2 a e wo disjoin ini e se o labels o memb anes; EC1=EC2a e he ini e se s o elec ical cha ges o memb anes; µ1and µ2a e he memb ane s uc u es con- sis ing ( esp.) o m1and m2memb anes labelled (no necessa ily in a one- o-one manne ) wi h elemen s o H1and H2;wi 1,...,wi ma e s ings o e Oi, desc ibing he mul ise s o objec s placed in he mi egions o µi( o i=1,2); R1and R2a e he ini e se s o ules associa ed o P1and P2. Le i1be he label o an elemen a y memb ane o P1and s2 he label o he skin memb ane o P2. And le µbe he memb ane s uc u e ob ained by iden i ying i1 wi h s2. Since he none i1is a lea e in µ1and he node s2is he oo o µ2 he new g aph is also a memb ane s uc u e. We keep he same label o all memb anes and label he join memb anes by α. We de ine a join P1◦P2as a P sys em P1◦P2= (O, H, EC, µ, w1,...,wm, R) whe e m=m1+m2−1is he ini ial deg ee o he sys ems; O=O1∪O2is he alphabe o objec s; H= (H1−{i1})∪(H2−{s2})∪{α}is he ini e se o labels o memb anes; EC =EC1=EC2is he ini e se o elec ical cha ges o memb anes; µand is he memb ane s uc u e labelled wi h elemen s o H;w1,...,wka e s ings o e O, desc ibing he mul ise s o objec s placed in he m egions o ; R=R1∪R2 is he ini e se o ules. 6 No e ha gi en wo P sys ems wi h he same se o elec ical cha ges (which can be emp y) he e exis s se e al posibili ies o ge ing a join : One o each elemen a y memb ane o P1. Nex we de ine he composi ion o wo P sys ems. In o de o de ine such composi ion we need wo P sys ems wi h inpu and ou pu . De ini ion 2 Le P1and P2be wo P sys ems wi h inpu and ou pu such ha : •The inpu memb ane o P1is an elemen a y memb ane. We will deno e by i1 he label o such memb ane. •The ou pu memb ane o P2is he skin memb ane. We will deno e by s2 he label o such memb ane. The composi ion P1◦P2is he join ob ained by iden i ying i1wi h s2. No e ha i P2sends he ou pu o he en i onmen , we can conside a new ex e nal memb ane su ounding he whole P sys em which becomes he new skin. Wi h his new skin we can conside he composi ion wi h ano he P sys em. 5. A Case S udy In his sec ion we desc ibe wo amiles o P sys ems ΠBans Ppa : •The amily ΠB={PB(n, d) : n, d ∈N}con e s mul ise s o na u al num- be s om bina y in o una y no a ion. The P sys em PB(n, d) depends on he numbe o elemen s ha we wan o con e and on d, whe e dis de ined by d=En [log2(max A)] + 1 (2) whe e Ais he se o numbe s o con e . •The amily Πpa ={Ppa (n) : n, ∈N}is a uni o m amily which sol es he NP-p oblem Pa i ion. I is based on he solu ion p esen ed in ... bu wi h small changes. Each P sys em Ppa (n) sol es all ins ances o he p oblem wi h nelemen s. The solu ion is ob ained in polynomial ime on nand he inpu has o be p o ided in una y o m. Bo h amilies a e designed wi h inpu and ou pu and i has sense o conside he composi ion o P sys ems o bo h amilies. We ob ain he ollowing amily: Π = {Ppa (n)◦PB(n, d) : n, d ∈N} whe e each P sys em P(n, d) = Ppa (n)◦PB(n, d) is a cellula de ice which sol es all he ins ances o he Pa i ion p oblem wi h he same pa ame e s nand d. 5.1. The amily ΠB The P sys ems o his amily a e adap ed om he model p esen ed in he sec ion ??. The di e ences a e mainly wo: Two memb anes a e conside ed, one as inpu memb ane and he second one ( he skin) is he ou pu memb ane. In his way we p epa e he composi ion wi h P sys ems o he second amily. 7 The second di e ence is due o echnical easons. We add new elemen s which has no meaning in he encoding o he in o ma ion, bu hey make sense a e he composi ion (objec s e0,zand ) and a coun e 1. The p oblem can be s a ed as ollows: Gi en a mul ise Ao na u al numbe s exp essed in bina y o m, o ge a mul ise A′wi h such numbe s exp essed in bina y o m. We adap he desc ip ion om sec ion e sec:enc. Ins ead o codi ying a single na u al numbe , we look o a P sys em which con e a mul ise o numbe s. So, o each elemen in he mul ise , we conside a ma k {x1, x2,...}, so in his way, ollowing sec ion ?? he mul ise {3,4,3,11}can be exp essed in bina y o m as he se o pai s {(x1,1),(x1,1),(x2,3),(x3,1),(x3,2),(x4,1)(x4,2),(x4,4)} whe e (xi, j) ep esen s ha he i− h elemen in he enume a ion o he mul ise has one in he j− h posi ion o he bina y ep esen a ion. We de ine he amily ΠB={PB(n, d) : n, d ∈N}whe e each PB(n, d) sol es all he ins ances o he p oblem wi h he same numbe o elemen s nand he same bound d, de ined in he equa ion ??. (In ac , hese nand da e uppe bounds). The P sys em PB(n, d) = (O(n, d), H, EC, µ, w , ws,...,R(n, d)) is de ined as ollows: •O(n, d) = {e0, z, }∪{y1,...,yn}∪{ 1,..., d+1} ∪ {(xi, j) : 1 ≤i≤n, 1≤j≤d} •H={ , s}wi h he label o he inpu memb ane and s, he skin he label o he ou pu memb ane. •EC =∅(We can also conside he memb anes wi h neu al cha ge along all he compu a ion) •µ= [ [ ] ]s •w ={e0, , 1};ws=∅ •The ollowing se o ules R(n, d): [(xi, j)→(xi, j −1)] o all i∈ {1,...n}and j∈ {1,...,d}. [(xi,1) →yi] o all i∈ {1,...n}. [ j→ j+1] o all j∈ {1,...,d}. [ d+1] →z. All he ules a e associa ed o he label and a e objec e olu ion ule. The only excep ion is he las one, which is a dissolu ion ule. A he beginning o he compu a ion, he inpu codi ying he mul ise o na u al numbe s in bina y o m (as desc ibed abo e) is placed in he inpu memb ane. The P sys em e ol es as desc ibed in sec ion ??. A e ds eps he memb ane con ains he elemen s e0, , d+1 and a mul ise o elemen s yi, 1 ≤i≤ncodi ying he inpu . In he nex s ep d+1 dissol es he memb ane and is ans o med in o zin 8 he skin. The emaining objec s also go o he skin. No mo e ules can be applied and he compu a ion hal s. The compu a ion is de e minis ic and hal s a e d+ 1 s eps. 5.2. The amily Πpa This amily is a uni o m amilyco P sys ems in he amewo k o ac i e mem- b anes (see ...) which sol es he NP-p oblem Pa i ion. I is based on he solu ion p esen ed in ... bu wi h small changes. Each P sys em Ppa (n) sol es all ins ances o he p oblem wi h nelemen s. The solu ion is ob ained in polynomial ime on nand he inpu has o be p o ided in una y o m. Each P syss em o he amily, Ppa (n), n, ∈Nconsis s on he ollowing elemen s: •O(n) = {a0, a, b0, b, c, d0, d1, d2, , 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, , s}; he skin s, he label e o he wo king memb anes and a label o he memb ane o con ol. •EC ={+,−,0} •µ= [ [ ] [ ]e]s •we=∅;ws=∅;w ={b0, h0} •The se o ules R(n) desc ibed below. We ollow he design o sol ing PAR- TITION wi h ac i e memb anes p esen ed in ..., wi h small changes due o echnical easons. A de ailed desc ip ion and mo i a ion o he ules can be ound he e. cIn he sense o ... 9