Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards

Res ic ed Pola iza ionless P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds Luis Valencia-Cab e a, Da id O ellana-Ma ´ın, Miguel ´ A. Ma ´ınez-del-Amo , Agus ´ın Riscos-N´u˜nez, Ma io J. P´e ez-Jim´enez Resea ch G oup on Na u al Compu ing Depa men o Compu e Science and A i icial In elligence Uni e sidad de Se illa A da. Reina Me cedes s/n, 41012 Se illa, Spain E-mail: {l alencia, do ellana, mdelamo , a iscosn, ma pe }@us.es Summa y. Memb ane compu ing is a compu ing pa adigm p o iding a class o dis- ibu ed pa allel compu ing de ices o a biochemical ype whose p ocess uni s ep esen biological memb anes. In he cell-like basic model, a hie a chical memb ane s uc u e o mally desc ibed by a oo ed ee is conside ed. I is well known ha amilies o such sys ems whe e he numbe o memb anes can only dec ease du ing a compu a ion ( o ins ance by dissol ing memb anes), can only sol e in polynomial ime p oblems in class P.P sys ems wi h ac i e memb anes is a a ian whe e memb anes play a cen al ole in hei dynamics. In he seminal e sion, memb anes ha e an elec ical pola iza ion (posi- i e, nega i e, o neu al) associa ed in any ins an , and besides being dissol ed, hey can also eplica e by using di ision ules. These sys ems a e compu a ionally uni e sal, ha is, equi alen in powe o de e minis ic Tu ing machines, and compu a ionally e icien , ha is, able o sol e compu a ionally ha d p oblems in polynomial ime. I pola iza ions in memb anes a e emo ed and dissolu ion ules a e o bidden, hen only p oblems in class Pcan be sol ed in polynomial ime by hese sys ems (e en in he case when di i- sion ules o non-elemen a y memb anes a e pe mi ed). In ha amewo k i has been shown ha by conside ing minimal coope a ion (le -hand side o such ules consis s o a mos wo symbols) and minimal p oduc ion (only one objec is p oduced by he appli- ca ion o such ules) in objec e olu ion ules, such sys ems p o ide e icien solu ions o NP–comple e p oblems. In his pape , minimal coope a ion and minimal p oduc ion in communica ion ules ins ead o objec e olu ion ules is s udied, and he compu a ional e iciency o hese sys ems is ob ained in he case whe e di ision ules o non-elemen a y memb anes a e pe mi ed. Key wo ds: Memb ane Compu ing, pola iza ionless P sys ems wi h ac i e mem- b anes, coope a i e ules, he P e sus NP p oblem, SAT p oblem. 254 L. Valencia-Cab e a e al. 1 In oduc ion Memb ane Compu ing is an eme gen b anch o Na u al Compu ing p o iding dis ibu ed pa allel and non-de e minis ic compu ing models whose compu a ional de ices a e called memb ane sys ems ha ing uni s p ocesso called compa men s. This compu ing pa adigm is inspi ed by some basic biological ea u es, by he s uc u e and unc ioning o he li ing cells, as well as om he coope a ion o cells in issues, o gans, and o ganisms. Celllike memb ane sys ems use he biological memb anes a anged hie a chically, inspi ed om he s uc u e o he cell. In Memb ane Compu ing, some a ian s cap u e he ac ha memb anes a e no a all passi e om a biochemis y iew, o ins ance, he passing o a chem- ical compound h ough a memb ane is o en done by a di ec in e ac ion wi h he memb ane i sel . Some a ian s o P sys ems whe e he cen al ole in hei dynamics is played by he memb anes ha e been conside ed. In hese models, he memb anes no only di ec ly media e he e olu ion and he communica ion o ob- jec s, bu hey can eplica e hemsel es by means o a di ision p ocess. Inspi ed by hese ea u es, P sys ems wi h ac i e memb anes [6] we e in oduced, based on p ocessing mul ise s by means o non-coope a i e ew i ing ules, ha is, ules whe e i s le -hand side has a mos only one objec . Speci ically, objec s e ol e inside memb anes which can communica e be ween each o he , can dissol e, and mo eo e (inspi ed by cellula mi osis p ocess) can eplica e by means o di ision ules. I is assumed ha each memb ane has associa ed an elec ical pola iza ion in any ins an , one o he h ee possible: posi i e, nega i e, o neu al. P sys ems wi h ac i e memb anes a e compu a ionally comple e, ha is, any ecu si ely enume able se o ec o s o na u al numbe s (in pa icula , each e- cu si ely enume able se o na u al numbe s) can be gene a ed by such a sys em [6]. Hence, hey a e equi alen in powe o de e minis ic Tu ing machines. Wha abou he compu a ional e iciency o P sys ems wi h ac i e memb anes? The key is ce ainly in he use o di ision ules, as we can deduce om he so- called Milano heo em [13]: A de e minis ic P sys em wi h ac i e memb anes bu wi hou memb ane di ision can be simula ed by a de e minis ic Tu ing machine wi h a polynomial slowdown. Howe e , P sys ems wi h ac i e memb anes which make use o di ision ules ha e he abili y o p o ide e icien solu ions o compu a ionally ha d p oblems, by making use o an exponen ial wo kspace c ea ed in a polynomial ime. Speci ically, NP-comple e p oblems can be sol ed in polynomial ime by amilies o P sys ems wi h ac i e memb anes, wi hou dissolu ion ules and which use di ision ules only o elemen a y memb anes [6]. Mo eo e , he class o decision p oblems which can be sol ed by amilies o P sys ems wi h ac i e memb anes wi h dissolu ion ules and which use di ision o elemen a y and non-elemen a y memb anes is equal o PSPACE [8]. Consequen ly, he usual amewo k o P sys ems wi h ac i e memb anes and elec ical pola iza ions o sol ing decision p oblems seems o be oo powe ul om he compu a ional complexi y poin o iew. Wi h espec o he compu a ional e iciency, in he classical amewo k o P sys em wi h ac i e memb anes, dissolu ion ules play an “innocen ” ole as well as P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 255 di ision o non-elemen a y memb anes. Howe e , i elec ical cha ges a e emo ed hen hese kind o ules come o play a ele an ole. Speci ically, P sys ems wi h ac i e memb anes and wi hou elec ical cha ges we e ini ially s udied in [1, 2] by eplacing elec ical cha ges by he abili y o change he label o he memb anes. In his pape , pola iza ionless P sys ems wi h ac i e memb anes whe e labels o memb anes keep unchanged by he applica ion o ules, a e conside ed. In his new amewo k, i dissolu ion ules a e o bidden hen only p oblems in class P can be sol ed in an e icien way, e en in he case ha di ision o non-elemen a y memb anes a e pe mi ed [5]. Is he class o pola iza ionless P sys ems wi h ac i e memb anes, wi h dissolu ion bu using only di ision ules o elemen a y mem- b anes compu a ionally e icien ? I P6=NP, which is a all expec ed, hen i is an open ques ion, so-called P˘aun’s conjec u e. In he seminal pape whe e P sys ems wi h ac i e memb anes we e in o- duced, Gh. P˘aun says ha “wo king wi h non-coope a i e ules is na u al om a ma hema ical poin o iew bu om a biochemical poin o iew his is no only non-necessa y, bu also non- ealis ic: mos o he chemical eac ions in ol e wo o mo e han wo chemical compounds (and also p oduce wo o mo e han wo compounds)”. In his con ex , a es ic ed coope a ion has been conside ed in he classical amewo k o pola iza ionless P sys ems wi h ac i e memb anes. Speci i- cally, minimal coope a ion ( he le -hand side and he igh -hand side o any ules ha e, a mos , wo objec s) in objec e olu ion ules, has been p e iously s ud- ied om a compu a ional complexi y poin o iew. A polynomial- ime solu ion o he SAT p oblem by means o amilies o pola iza ionless P sys ems wi h ac i e memb anes, wi h minimal coope a ion in objec e olu ion ules, has been p o ided [9]. Recen ly, his esul has been imp o ed by conside ing minimal coope a ion in objec e olu ion ules wi h and addi ional es ic ion: he igh -hand side o any ules has only one objec (called minimal coope a ion and minimal p oduc ion) [11]. A ele an ac in hese esul s is he ollowing: dissolu ion ules and di ision ules o non-elemen a y memb anes a e no necessa y o each he compu a ional e iciency. In his pape he ole o minimal coope a ion and minimal p oduc ion in com- munica ion ules ins ead o objec e olu ion ules, is s udied om a complexi y poin o iew. Speci ically, by using amilies o memb ane sys ems which use hese syn ac ical ing edien s, a polynomial- ime solu ion o he SAT p oblem is p o ided bu allowing di ision ules o non-elemen a y memb anes. The pape is s uc u ed as ollows. Fi s , some basic no ions a e ecalled and he e minology and no a ion o be used in he pape is p esen ed. Then, Sec ion 3 in oduces he model ha will be in es iga ed in his pape : pola iza ionless P sys- ems wi h ac i e memb anes, wi h minimal coope a ion and minimal p oduc ion in hei communica ion ules. Sec ion 4 con ains he main esul o his pape , showing ha hese sys ems a e capable o sol ing an NP-comple e p oblem in an e icien way. Finally, he pape concludes wi h some inal ema ks and ideas o u u e wo k. 256 L. Valencia-Cab e a e al. 2 P elimina ies An alphabe Γis a non-emp y se and hei elemen s a e called symbols. A s ing u o e Γis an o de ed ini e sequence o symbols, ha is, a mapping om a na u al numbe n∈Non o Γ. The numbe nis called he leng h o he s ing uand i is deno ed by |u|. The emp y s ing (wi h leng h 0) is deno ed by λ. The se o all s ings o e an alphabe Γis deno ed by Γ∗. A language o e Γis a subse o Γ∗. Amul ise o e an alphabe Γis an o de ed pai (Γ, ) whe e is a mapping om Γon o he se o na u al numbe s N. The suppo o a mul ise m= (Γ, ) is de ined as supp(m) = {x∈Γ| (x)>0}. A mul ise is ini e ( espec i ely, emp y) i i s suppo is a ini e ( espec i ely, emp y) se . We deno e by ∅ he emp y mul ise . Le m1= (Γ, 1), m2= (Γ, 2) be mul ise s o e Γ, hen he union o m1 and m2, deno ed by m1+m2, is he mul ise (Γ, g), whe e g(x) = 1(x) + 2(x) o each x∈Γ. We deno e by M (Γ) he se o all mul ise s o e Γ. 2.1 G aphs and ees Le us ecall some no ions ela ed wi h g aph heo y (see [3] o de ails). An undi ec ed g aph is an o de ed pai (V, E) whe e Vis a se whose elemen s a e called nodes o e ices and E={{x, y} | x∈V, y ∈V, x 6=y}whose elemen s a e called edges. A pa h o leng h k≥1 om a node u o a node in a g aph (V, E) is a ini e sequence (x0, x1, . . . , xk) o nodes such ha x0=u,xk= and {xi, xi+1} ∈ E. I k≥2 and x0=xk hen we say ha he pa h is a cycle o he g aph. A g aph wi h no cycle is said o be acyclic. An undi ec ed g aph is connec ed i he e exis pa hs be ween e e y pai o nodes. A oo ed ee is a a connec ed, acyclic, undi ec ed g aph in which one o he e ices (called he oo o he ee) is dis inguished om he o he s. Gi en a node x(di e en om he oo ), i he las edge on he (unique) pa h om he oo o he ee o he node xis {x, y}(in his case, x6=y), hen yis he pa en o node xand xis achild o node y. The oo is he only node in he ee wi h no pa en . A node wi h no child en is called a lea . 2.2 The Can o pai ing unc ion The Can o pai ing unc ion encodes pai s o na u al numbe s by single na u al numbe s, and i is de ined as ollows: o each n, p ∈N hn, pi=(n+p)(n+p+ 1) 2+n The Can o pai ing unc ion is a p imi i e ecu si e unc ion and bijec i e om N×Non o N. Then, o each ∈N he e exis unique na u al numbe s n, p ∈N such ha =hn, pi. P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 257 2.3 Decision p oblems and languages A decision p oblem Xis an o de ed pai (IX, θX), whe e IXis a language o e a ini e alphabe ΣXand θXis a o al Boolean unc ion o e IX. The elemen s o IXa e called ins ances o he p oblem X. Each decision p oblem Xhas associa ed a language LXo e he alphabe ΣXas ollows: LX={u∈ΣX ∗|θX(u)=1}. Con e sely, e e y language Lo e an alphabe Σhas associa ed a decision p oblem XL= (IXL, θXL) as ollows: IXL=Σ∗and θXL(u) = 1 i and only i u∈L. The e o e, gi en a decision p oblem Xwe ha e XLX=X, and gi en a language Lo e an alphabe Σwe ha e LXL=L. Then, sol ing a decision p oblem can be exp essed equi alen ly as he ask o ecognizing he language associa ed wi h i . 2.4 Recognize memb ane sys ems Recognize memb ane sys ems we e in oduced in [7] and hey p o ide a na u al amewo k o sol e decision p oblems. This kind o sys ems a e cha ac e ized by he ollowing ea u es: (a) he wo king alphabe Γhas wo dis inguished objec s yes and no; (b) he e exis s an inpu memb ane and an inpu alphabe Σs ic ly con ained in Γ; (c) he ini ial con en s o he memb anes a e mul ise s o e Γ Σ; (d) all compu a ions hal ; and (e) o each compu a ion, ei he objec yes o objec no (bu no bo h) mus ha e been eleased in o he en i onmen , and only a he las s ep o he compu a ion. Gi en a ecognize memb ane sys em, Π, o each mul ise mo e he inpu alphabe Σwe deno e by Π+m he memb ane sys em Πwi h inpu mul ise m, ha is in he ini ial con igu a ion o ha sys em, he mul ise mis added o he ini ial con en o he inpu memb ane. Thus, in a ecognize memb ane sys em, Π, he e exis s an ini ial con igu a ion associa ed wi h each mul ise m∈M (Σ). 3 Minimal coope a ion and minimal p oduc ion in communica ion ules De ini ion 1. A pola iza ionless P sys em wi h ac i e memb anes, wi h simple objec e olu ion ules, wi hou dissolu ion, wi h di ision ules o elemen a y and non-elemen a y memb anes, and which makes use o minimal coope a ion and minimal p oduc ion in send-ou communica ion ules, is a uple Π= (Γ, Σ, H, µ, M1,...,Mq,R, iin, iou ) whe e: •Γis a ini e alphabe whose elemen s a e called objec s and con ains wo dis- inguished objec s yes and no. •Σ(Γis he inpu alphabe . 258 L. Valencia-Cab e a e al. •His a ini e alphabe such ha H∩Γ=∅whose elemen s a e called labels. •q≥1is he deg ee o he sys em. •µis a labelled oo ed ee (called memb ane s uc u e)consis ing o qnodes injec i ely labelled by elemen s o H( he oo o µis labelled by µ). • M1,...,Mqa e mul ise s o e Γ Σ. • R is a ini e se o ules, o he ollowing o ms: (a0) [ a→b]h, whe e h∈H,a, b ∈Γ,u∈M (Γ) (simple objec e olu ion ules). (b0)a[ ]h→[b]h, whe e h∈H { µ},a, b, c ∈Γ(send–in communica ion ules). (c0) [ a b ]h→c[ ]h, whe e h∈H,a, b ∈Γ(send–ou communica ion ules wi h minimal coope a ion and minimal p oduc ion). (d0) [ a]h→b, whe e h∈H {iou , µ},a, b ∈Γ(dissolu ion ules). (e0) [ a]h→[b]h[c]h, whe e h∈H {iou , µ},a, b, c ∈Γand his he label o an elemen a y memb ane µ(di ision ules o elemen a y memb anes). ( 0) [ [ ]h1[ ]h2]h0→[ [ ]h1]h0[ [ ]h2]h0, whe e h0, h1, h2∈Hand h06= µ(di i- sion ules o non-elemen a y memb anes). •iin ∈H,iou ∈H∪ {en }(i iou ∈H hen iou is he label o a lea o µ). In a simila way is de ined he concep o “pola iza ionless P sys em wi h ac i e memb anes, wi h simple objec e olu ion ules, wi hou dissolu ion, wi h di ision ules o elemen a y and non-elemen a y memb anes, and which makes use o minimal coope a ion and minimal p oduc ion in send-in communica ion ules ”. The only di e ence conce ns ules o ype (b0) and (c0). In his case a e, espec- i ely: (b0 0)a b [ ]h→[c]h o h∈H { µ},a, b ∈Γ(send–in communica ion ules wi h minimal coope a ion and minimal p oduc ion). (c0 0) [ a]h→b[ ]h o h∈H,a, b, c ∈Γ(send–ou communica ion ules). The seman ics o his kind o P sys ems ollows he usual p inciples o P sys ems wi h ac i e memb anes [6]. We deno e by DAM0(+es, mcmpou ,−d, +n) ( espec i ely, DAM0(+es, mcmpin,−d, +n)) he class o all ecognize pola iza ionless P sys em wi h ac i e memb anes, wi h simple objec e olu ion ules, wi hou dissolu ion, wi h di ision ules o elemen a y and non-elemen a y memb anes, which make use o minimal coope a ion and minimal p oduc ion in send-ou ( espec i ely, send-in) communica ion ules. 4 Sol ing SAT in DAM0(+es, mcmpou ,−d, +n) In his sec ion, a polynomial- ime solu ion o SAT p oblem, is explici ly gi en in he amewo k o ecognize pola iza ionless P sys ems wi h ac i e memb anes P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 259 wi h simple objec e olu ion ules, wi hou dissolu ion and wi h di ision ules o elemen a y and non-elemen a y memb anes which make use o minimal coope a- ion and minimal p oduc ion in send-in communica ion ules. Fo ha , a amily Π={Π( )| ∈N}o ecognize P sys ems om DAM0(+es, mcmpou ,−d, +n) will be p esen ed. 4.1 Desc ip ion o a solu ion o SAT p oblem in DAM0(+es, mcmpou ,−d, +n) Fo each n, p ∈N, we conside he ecognize P sys em Π(hn, pi)=(Γ, Σ, H, µ, M0,M1,M2,R, iin, iou ) om DAM0(+es, mcmpou ,−d, +n), de ined as ollows: (1)Wo king alphabe : Γ=Σ∪ {yes ,no ,#}∪{ai,k |1≤i≤n∧1≤k≤2i−1} ∪ {αk|0≤k≤4np +n+ 2p} ∪ {βk|0≤k≤4np +n+ 2p+ 1} ∪ {γk|0≤k≤4np +n} ∪ { i,k, i,k |1≤i≤n∧2i−1≤k≤2n+ 2p−1} ∪ {Ti, Fi|1≤i≤n} ∪ {cj|1≤j≤p} ∪ {cj,k |1≤j≤p∧0≤k≤np −1}∪{dj|1≤j≤p} ∪ {xi,j,k, xi,j,k, x∗ i,j,k |1≤i≤n∧1≤j≤p∧ 1≤k≤n+ 2np +n(j−1) + (i−1)} whe e he inpu alphabe is Σ={xi,j,0, xi,j,0, x∗ i,j,0|1≤i≤n∧1≤j≤p}; (2)H={0,1,2}; (3)Memb ane s uc u e: µ= [ [ [ ]2]1]0, ha is, µ= (V, E) whe e V={0,1,2} and E={(0,1)(1,2)} (4)Ini ial mul ise s: M0={α0, β0},M1=∅,M2={γ0} ∪ {ai,1, T p i, Fp i|1≤i≤ n}. (5)The se o ules Rconsis s o he ollowing ules: 5.1Coun e s o synch onize he answe o he sys em. [αk−→ αk+1 ]0, o 0 ≤k≤4np +n+ 2p−1 [βk−→ βk+1 ]0, o 0 ≤k≤4np +n+ 2p [γk−→ γk+1 ]2, o 0 ≤k≤4np +n−1 5.2Rules o gene a e 2nmemb anes labelled by 1 and 2nmemb anes labelled by 2 ( hese encoding all possible u h assignmen o n a iables o he inpu o mula). [ai,2i−1]2−→ [ i,i ]2[ i,i ]2, o 1 ≤i≤n [ai,j −→ ai,j+1 ]2, o 2 ≤i≤n, 1≤j≤2i−2 [ [ ]2[ ]2]1−→ [ [ ]2]1[ [ ]2]1 [ i,j −→ i,j+1 ]2 [ i,j −→ i,j+1 ]2, o 1 ≤i≤n, i ≤j≤2n−1 260 L. Valencia-Cab e a e al. 5.3Rules o p oduce exac ly pcopies o each u h assignmen encoded by memb anes labelled by 2. [ i,2jn Fi]2−→ i,2jn+1 [ ]2 [ i,2jn Ti]2−→ i,2jn+1 [ ]2 i,(2j+1)n[ ]2−→ [ i,(2j+1)n+1 ]2 i,(2j+1)n[ ]2−→ [ i,(2j+1)n+1 ]2        , o 1 ≤i≤n, 1≤j≤p−1 [ i,2np Fi]2−→ # [ ]2 [ i,2np Ti]2−→ # [ ]2, o 1 ≤i≤n [ i,(2j+1)n+k−→ i,(2j+1)n+k+1 ]2 [ i,(2j+1)n+k−→ i,(2j+1)n+k+1 ]2 [ i,2jn+k−→ i,2jn+k+1 ]1 [ i,2jn+k−→ i,2jn+k+1 ]1        , o 1≤i≤n, 1≤j≤p−1, 1≤k≤n−1 5.4Rules o p epa e he inpu o mula o check clauses: [xi,j,k −→ xi,j,k+1 ]2 [xi,j,k −→ xi,j,k+1 ]2 [x∗ i,j,k −→ x∗ i,j,k+1 ]2   , o 1≤i≤n, 1≤j≤p, 0≤k≤2np +n+n(j−1) + (i−1) −1 5.5Rules implemen ing he i s checking s age. [Tixi,j,2np+n+n(j−1)+(i−1)]2−→ cj,0[ ]2 [Tixi,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Tix∗ i,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Fixi,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Fixi,j,2np+n+n(j−1)+(i−1)]2−→ cj,0[ ]2 [Fix∗ i,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2                , o 1≤i≤n, 1≤j≤p 5.6Rules implemen ing he second checking s age. [cj,k −→ cj,k+1 ]1, o 1 ≤j≤p, 0≤k≤np −2 cj,np−1[ ]2−→ [cj]2, o 1 ≤j≤p [γ4np+nc1]2−→ d1[ ]2 [djcj+1 ]2−→ dj+1[ ]2 dj[ ]2−→ [dj]2, o 1 ≤j≤p−1 5.7Rules o p o ide he co ec answe o he sys em. [dp]1−→ dp[ ]1 [α4np+n+2pdp]0−→ yes [ ]0 [α4np+n+2pβ4np+n+2p+1 ]0−→ no [ ]0 (6) he inpu memb ane is he memb ane labelled by 2 (iin = 2) and he ou pu egion is he en i onmen (iou =en ). 5 A o mal e i ica ion Le ϕ=C1∧. . . ∧Cpan ins ance o SAT p oblem consis ing o pclauses Cj=lj,1∨. . . ∨lj, j, 1 ≤j≤p, whe e V a (ϕ) = {x1, . . . , xn}, and lj,k ∈ P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 261 {xi,¬xi|1≤i≤n}, 1 ≤j≤p, 1 ≤k≤ j. Le us asume ha he numbe o a iables, n, and he numbe o clauses, p, o ϕ, a e g ea e o equal o 2. We conside he polynomial encoding (cod, s) om SAT in Πde ined as ollows: Fo each ϕ∈ISAT wi h n a iables and pclauses, s(ϕ) = hn, piand cod(ϕ) = {xi,j,0|xi∈Cj}∪{xi,j,0|¬xi∈Cj}∪{x∗ i,j,0|xi6∈ Cj,¬xi6∈ Cj} Fo ins ance, he o mula ϕ= (x1+x2+x3)(x2+x4)(x2+x3+x4) is encoded as ollows: cod(ϕ) =   x1,1,0x2,1,0x3,1,0x∗ 4,1,0 x∗ 1,2,0x2,2,0x∗ 3,2,0x4,2,0 x∗ 1,3,0x2,3,0x3,3,0x4,3,0   Tha is, j- h ow (1 ≤j≤p) ep esen s he j- h clause Cjo ϕ. We deno e (cod(ϕ))p j he code o he clauses Cj, . . . , Cp, ha is, he exp ession con aining om j- h ow o p- h ow. Fo ins ance, cod(ϕ)p 2=x∗ 1,2,0x2,2,0x∗ 3,2,0x4,2,0 x∗ 1,3,0x2,3,0x3,3,0x4,3,0 We deno e (codk(ϕ))p j) he code cod(ϕ)p jwhen he hi d index o he a iables equal 3. Fo ins ance: ow o p- h ow. Fo ins ance, cod3(ϕ)p 2=x∗ 1,2,3x2,2,3x∗ 3,2,3x4,2,3 x∗ 1,3,3x2,3,3x3,3,3x4,3,3 We deno e (cod0 k(ϕ))p j) he code cod(ϕ)p jwhen he hi d index o he a iables equal 3. Fo ins ance: ow o p- h ow. Fo ins ance, cod0 3(ϕ)p 2=x∗0 1,2,3x0 2,2,3x∗0 3,2,3x0 4,2,3 x∗0 1,3,3x0 2,3,3x0 3,3,3x0 4,3,3 We deno e (cod∗(ϕ))p j) he code cod(ϕ)p jwhen he hi d index does no exis . Fo ins ance: ow o p- h ow. Fo ins ance, cod∗(ϕ)p 2=x∗1,2x2,2x∗ 3,2x4,2 x∗1,3x2,3x3,3x4,3 The Boolean o mula ϕwill be p ocessed by he sys em Π(s(ϕ)) + cod(ϕ). Nex , we in o mally desc ibe how ha sys em wo ks. The solu ion p oposed ollows a b u e o ce algo i hm in he amewo k o ecognize P sys ems wi h ac i e memb anes, minimal coope a ion in objec e o- lu ion ules and di ision ules only o elemen a y memb anes, and i consis s o he ollowing s ages: •Gene a ion s age: using sepa a ion ules, beside o he ules ha make a “simula ion” o di ision ules, we ge all u h assignmen s o he a iables {x1, . . . , xn}associa ed wi h ϕa e p oduced. Speci ically, 2nmemb anes la- belled by 1 and 2nlabelled by 2 a e gene a ed. Each o he o me ones encodes a u h assignmen . This s age akes exac ly n+2np s eps, being n he numbe o a iables o ϕ. 268 L. Valencia-Cab e a e al. - a con igu a ion C3nwe ha e C3n(0) = {α3n, β3n}and he e exis 2n memb anes labelled by 1 con aining and a di e en subse o objec s i,3n+1−i, 1 ≤i≤n, being ∈ { , }, ha is, he co esponding u h assignmen o he b anch; and 2nmemb anes labelled by 2 con aining he inpu mul ise cod3n(ϕ), an objec γ3n,pcopies o Tiand Fi, being 1≤i≤ni he u h assignmen associa ed o he b anch con ains i s co esponding objec io i,p−1 objec s o he wise. Then, con igu a ion C3nyields con igu a ion C3n+1 by applying he ules: 1,3n[ ]2→[ 1,3n+1 ]2 1,3n[ ]2→[ 1,3n+1 ]2 [ i,3n−i+1 → i,3n−i+2 ]1 [ i,3n−i+1 → i,3n−i+2 ]1 o 2 ≤i≤n [α3n→α3n+1 ]0 [β3n→β3n+1 ]0 [γ3n→γ3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [x∗ i,j,3n→x∗ i,j,3n+1 ]2    o 1 ≤i≤n, 1≤j≤p Thus, C3n+1(0) = {α3n+1, β3n+1}, and he e exis 2nmemb anes la- belled by 1 con aining a di e en subse o objec s i,3n−i+2, 2 ≤i≤n, being ∈ { , }; and 2nmemb anes labelled by 2 con aining he in- pu mul ise cod3n+1(ϕ), an objec γ3n+1,pcopies o Tiand Fi, being 1≤i≤ni he u h assignmen associa ed o he b anch con ains i s co esponding objec io i,p−1 objec s o he wise and an objec 1,3n+1, being ∈ { , }. - Supposing, by induc ion, esul is ue o k(1 ≤k≤n) -C3n+k(0) = {α3n+k, β3n+k} - In C3n+k he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,3n+k−i+1,k+ 1 ≤i≤n, being ∈ { , }. - In C3n+k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod3n+k(ϕ); ?an objec γ3n+k; ? p copies o e e y Tiand Fi o 1 ≤i≤no hei co esponding i o iis assigned o ha b anch, p−lcopies o he wise; and ?a di e en subse o objec s i,3n+k−i+1, 1 ≤i≤k, being ∈ { , }. Then, con igu a ion C3n+kyields con igu a ion C3n+k+1 by applying he ules: k+1,3n[ ]2→[ k+1,3n+1 ]2 k+1,3n[ ]2→[ k+1,3n+1 ]2 [ i,3n+k−i+1 → i,3n+k−i+2 ]1 [ i,3n+k−i+1 → i,3n+k−i+2 ]1 o k+ 2 ≤i≤n [ i,3n+k−i+1 → i,3n+k−i+2 ]2 [ i,3n+k−i+1 → i,3n+k−i+2 ]2 o 1 ≤i≤k P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 269 [α3n+k→α3n+k+1 ]0 [β3n+k→β3n+k+1 ]0 [γ3n+k→γ3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [x∗ i,j,3n+k→x∗ i,j,3n+k+1 ]2    o 1 ≤i≤n, 1≤j≤p The e o e, he ollowing holds -C3n+k+1(0) = {α3n+k+1, β3n+k+1} - In C3n+k+1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,3n+k−i+2,k+ 2 ≤i≤n, being ∈ { , }. - In C3n+k+1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod3n+k+1(ϕ); ?an objec γ3n+k+1; ? p copies o e e y Tiand Fi o 1 ≤i≤no he co esponding io iis assigned o ha b anch, p−lcopies o he wise; and ?a di e en subse o objec s i,3n+k−i+2, 1 ≤i≤k+ 1, being ∈ { , }. - Supposing, by induc ion, esul is ue o l(0 ≤l≤p−1) (a0) The base case k= 1 is i ial because: - a con igu a ion C2n+(l+1)n1we ha e: C2n+(l+1)n(0) = {α2n+(l+1)n, β2n+(l+1)n}and he e exis 2nemp y memb anes labelled by 1; and 2n memb anes labelled by 2 con aining he inpu mul ise cod2n+(l+1)n(ϕ), an objec γ2n+(l+1)n,pcopies o Tiand Fi, being 1 ≤i≤n, and p−l copies o Ti( esp. Fi) objec s ha a e in a b anch wi h an objec i ( esp. i) and a di e en subse o objec s i,2n+(l+1)n−i+1, 1 ≤i≤n, be- ing ∈ { , }, he co esponding u h assignmen o he b anch. Then, con igu a ion C2n+(l+1)nyields con igu a ion C2n+(l+1)n+1 by applying he ules: [ i,2n+(l+1)nFi]2→ i,2n+(l+1)n+1[ ]2 [ i,2n+(l+1)nTi]2→ i,2n+(l+1)n+1[ ]2 [ i,2n+(l+1)n+1−i→ i,2n+(l+1)n+2−i]2 [ i,2n+(l+1)n+1−i→ i,2n+(l+1)n+2−i]2 o 2 ≤i≤n [α2n+(l+1)n→α2n+(l+1)n+1 ]0 [β2n+(l+1)n→β2n+(l+1)n+1 ]0 [γ2n+(l+1)n→γ2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [x∗ i,j,2n+(l+1)n→x∗ i,j,2n+(l+1)n+1 ]2    o 1 ≤i≤n, 1≤j≤p Thus, C2n+(l+1)n+1(0) = {α2n+(l+1)n+1, β2n+(l+1)n+1}, and he e exis 2nmemb anes labelled by 1 con aining and an objec 1,2n+(l+1)n+1, 1No e ha (l+ 1)n=ln +n, and i has been demons a ed in he i s s ep o he induc ion ha i is co ec . 270 L. Valencia-Cab e a e al. being ∈ { , }; and 2nmemb anes labelled by 2 con aining he inpu mul ise cod2n+(l+1)n+1(ϕ), an objec γ2n+(l+1)n+1,pcopies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, o he wise p−lcopies o Fi( esp. Ti) i 2 ≤i≤n,p−l−1 o he wise and a di e en subse o objec s i,2n+(l+1)n−i+2, 2 ≤i≤n, being ∈ { , }. - Supposing, by induc ion, esul is ue o k(1 ≤k≤n) -C2n+(l+1)n+k(0) = {α2n+(l+1)n+k, β2n+(l+1)n+k} - In C2n+(l+1)n+k he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,2n+(l+1)n+k−i+1, 1 ≤i≤k, being ∈ { , }. - In C2n+(l+1)n+k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2n+(l+1)n+k(ϕ); ?an objec γ2n+(l+1)n+k; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i ( esp. i) objec exis s in ha b anch, o he wise p−lcopies o Fi ( esp. Ti) i k+ 1 ≤i≤n,p−l−1 o he wise; and ?a di e en subse o objec s i,2n+(l+1)n+k−i+1,k+ 1 ≤i≤n, being ∈ { , }. Then, con igu a ion C2n+kyields con igu a ion C2n+(l+1)n+k+1 by ap- plying he ules: [ k+1,2n+(l+1)nFk+1 ]2→ k+1,2n+(l+1)n+1[ ]2 [ k+1,2n+(l+1)nTk+1 ]2→ k+1,2n+(l+1)n+1[ ]2 [ i,2n+(l+1)n+k−i+1 → i,2n+k−i+2 ]2 [ i,2n+(l+1)n+k−i+1 → i,2n+k−i+2 ]2 o k+ 2 ≤i≤n [ i,2n+(l+1)n+k−i+1 → i,2n+(l+1)n+k−i+2 ]1 [ i,2n+(l+1)n+k−i+1 → i,2n+(l+1)n+k−i+2 ]1 o 1 ≤i≤k [α2n+(l+1)n+k→α2n+(l+1)n+k+1 ]0 [β2n+(l+1)n+k→β2n+(l+1)n+k+1 ]0 [γ2n+(l+1)n+k→γ2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [x∗ i,j,2n+(l+1)n+k→x∗ i,j,2n+(l+1)n+k+1 ]2    o 1 ≤i≤n, 1≤j≤p The e o e, he ollowing holds -C2n+(l+1)n+k+1(0) = {α2n+(l+1)n+k+1, β2n+(l+1)n+k+1} - In C2n+(l+1)n+k+1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,2n+(l+1)n+k−i+2, 1 ≤i≤k+1, being ∈ { , }. - In C2n+(l+1)n+k+1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2n+(l+1)n+k+1(ϕ); ?an objec γ2n+(l+1)n+k+1; P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 271 ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i ( esp. i) objec exis s in ha b anch, o he wise p−lcopies o Fi ( esp. Ti) i k+ 2 ≤i≤n,p−l−1 o he wise; and ?a di e en subse o objec s i,2n+(l+1)n+k−i+2,k+ 2 ≤i≤n, being ∈ { , }. (a1) The base case k= 1 is i ial because: - a con igu a ion C3n+(l+1)nwe ha e C3n+(l+1)n(0) = {α3n+(l+1)n, β3n+(l+1)n}and he e exis 2nmemb anes labelled by 1 con aining a di e en subse o objec s i,3n+(l+1)n−i+1, 1 ≤i≤n, being ∈ { , }, ha is, he co esponding u h assignmen o he b anch; and 2nmem- b anes labelled by 2 con aining he inpu mul ise cod3n+(l+1)n(ϕ), an objec γ3n+(l+1)nand pcopies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, and p−l copies o Fi( esp. Ti). Then, con igu a ion C3n+(l+1)nyields con igu a- ion C3n+(l+1)n+1 by applying he ules: 1,3n+(l+1)n[ ]2→[ 1,3n+(l+1)n+1 ]2 1,3n+(l+1)n[ ]2→[ 1,3n+(l+1)n+1 ]2 [ i,3n+(l+1)n−i+1 → i,3n+(l+1)n−i+2 ]1 [ i,3n+(l+1)n−i+1 → i,3n+(l+1)n−i+2 ]1 o 2 ≤i≤n [α3n+(l+1)n→α3n+(l+1)n+1 ]0 [β3n+(l+1)n→β3n+(l+1)n+1 ]0 [γ3n+(l+1)n→γ3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [x∗ i,j,3n+(l+1)n→x∗ i,j,3n+(l+1)n+1 ]2    o 1 ≤i≤n, 1≤j≤p Thus, C3n+(l+1)n+1(0) = {α3n+(l+1)n+1, β3n+(l+1)n+1}, and he e exis 2nmemb anes labelled by 1 con aining a di e en subse o objec s i,3n+(l+1)n−i+2, 2 ≤i≤n, being ∈ { , }; and 2nmemb anes la- belled by 2 con aining he inpu mul ise cod3n+(l+1)n+1(ϕ), an objec γ3n+(l+1)n+1,pcopies o Ti( esp. Fi) being 1 ≤i≤ni he co espond- ing i( esp. i) objec exis s in ha b anch, and p−lcopies o Fi( esp. Ti) and an objec 1,3n+(l+1)n+1, being ∈ { , }. - Supposing, by induc ion, esul is ue o k(1 ≤k≤n) -C3n+(l+1)n+k(0) = {α3n+(l+1)n+k, β3n+(l+1)n+k} - In C3n+(l+1)n+k he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,3n+k−i+1,k+ 1 ≤i≤n, being ∈ { , }. - In C3n+(l+1)n+k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod3n+(l+1)n+k(ϕ); ?an objec γ3n+(l+1)n+k; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i ( esp. i) objec exis s in ha b anch, and p−lcopies o Fi( esp. Ti) 272 L. Valencia-Cab e a e al. ?a di e en subse o objec s i,3n+(l+1)n−i+1, 1 ≤i≤k, being ∈ { , }. Then, con igu a ion C3n+(l+1)n+kyields con igu a ion C3n+(l+1)n+k+1 by applying he ules: k+1,3n+(l+1)n[ ]2→[ k+1,3n+(l+1)n+1 ]2 k+1,3n+(l+1)n[ ]2→[ k+1,3n+(l+1)n+1 ]2 [ i,3n+(l+1)n+k−i+1 → i,3n+(l+1)n+k−i+2 ]1 [ i,3n+(l+1)n+k−i+1 → i,3n+(l+1)n+k−i+2 ]1 o k+ 2 ≤i≤n [ i,3n+(l+1)n+k−i+1 → i,3n+(l+1)n+k−i+2 ]2 [ i,3n+(l+1)n+k−i+1 → i,3n+(l+1)n+k−i+2 ]2 o 1 ≤i≤k [α3n+(l+1)n+k→α3n+(l+1)n+k+1 ]0 [β3n+(l+1)n+k→β3n+(l+1)n+k+1 ]0 [γ3n+(l+1)n+k→γ3n+(l+1)n+k+1 ]2 [xi,j,3n+(l+1)n+k→xi,j,3n+(l+1)n+k+1 ]2 [xi,j,3n+(l+1)n+k→xi,j,3n+(l+1)n+k+1 ]2 [x∗ i,j,3n+(l+1)n+k→x∗ i,j,3n+(l+1)n+k+1 ]2    o 1 ≤i≤n, 1≤j≤p The e o e, he ollowing holds -C3n+(l+1)n+k+1(0) = {α3n+(l+1)n+k+1, β3n+(l+1)n+k+1} - In C3n+(l+1)n+k+1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains objec s i,3n+(l+1)n+k−i+2,k+2 ≤i≤n, being ∈ { , }. - In C3n+(l+1)n+k+1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod3n+(l+1)n+k+1(ϕ); ?an objec γ3n+(l+1)n+k+1; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i ( esp. i) objec exis s in ha b anch, and p−lcopies o Fi( esp. Ti) ?a di e en subse o objec s i,3n+(l+1)n+k−i+2, 1 ≤i≤k+ 1, being ∈ { , }. - In o de o p o e (b) i is enough o no ice ha , on he one hand, om (a) con igu a ion C2np−12holds: -C2np−1(0) = {α2np−1, β2np−1} - In C2np−1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains an objec n,2np, being ∈ { , }. - In Cn+2np−1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2np−1(ϕ); ?an objec γ2np−1; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o he wise; and ?a di e en subse o objec s i,2np−i, 1 ≤i≤n−1. 2No e ha 2np −1 = n+ 2n(p−1) + (n−1) P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 273 Then, con igu a ion Cn+2np−1yields Cn+2np by applying he ules: n,2np[ ]2→[ n,2np+1 ]2 n,2np[ ]2→[ n,2np+1 ]2 [ i,n+2np−i→ i,n+2np−i+1 ]2 [ i,n+2np−i→ i,n+2np−i]2 o 1 ≤i≤n−1 [αn+2np−1→αn+2np ]0 [βn+2np−1→βn+2np ]0 [γn+2np−1→γn+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [x∗ i,j,n+2np−1→x∗ i,j,n+2np ]2    o 1 ≤i≤n, 1≤j≤p Then, we ha e C2np(0) = {α2np, β2np}, and he e exis 2nemp y memb anes labelled by 1; and 2nmemb anes labelled by 2 con aining con aining he inpu mul ise cod2np(ϕ), an objec γ2np,pcopies o Ti( esp. Fi) being 1≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o he wise and a di e en mul ise o objec s i,2np−i+1, 1 ≤i≤n, being ∈ { , }, ha is, he u h assignmen associa ed wi h he b anch.  P oposi ion 3. Le C= (C0,C1,...,Cq)be a compu a ion o he sys em Π(s(ϕ)) wi h inpu mul ise cod(ϕ). (a)Fo each k(1≤k≤n−1) a con igu a ion C2np+kwe ha e he ollowing: -C2np+k(0) = {α2np+k, β2np+k} - The e a e 2nmemb anes labelled by 1 such ha each o hem con ains k objec s #. - he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2np+k(ϕ); ?an objec γ2np+k; ? p copies o Ti( esp. Fi) being 1≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o Fi( esp. Ti) i k+1 ≤i≤n; and ?objec s i,2np+k−i+1,k+ 1 ≤i≤n. (b)Cn+2np(0) = {αn+2np, βn+2np}, and in Cn+2np he e a e 2nmemb anes labelled by 1, such ha each o hem con ains nobjec s #; and 2nmemb anes labelled by 2, such ha each o hem con ains he inpu mul ise codn+2np(ϕ), an ob- jec γn+2np,pcopies o e e y Tiand Fi,1≤i≤ni he u h assignmen associa ed o he b anch con ains i s co esponding io iobjec . P oo . (a) is going o be demons a ed by induc ion on k - he base case k= 1 is i ial because: - a C2np we ha e C2np(0) = {α2np, β2np}and he e exis 2nemp y memb anes labelled by 1; and 2nmemb anes labelled by 2 con aining he inpu mul ise cod2np(ϕ), an objec γ2np pcopies o Ti( esp. Fi) being 1 ≤i≤ni 274 L. Valencia-Cab e a e al. he co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o he wise and a di e en mul ise o objec s i,2np−i+1, 1 ≤i≤n, being ∈ { , }, ha is, he u h assignmen associa ed wi h he b anch. Then, con igu a ion C2np yields C2np+1 by applying he ules. [ 1,2np F1]2→#[ ]2 [ 1,2np T1]2→#[ ]2 [ i,2np−i+1 → i,2np−i+2 ]2 [ i,2np−i+1 → i,2np−i+2 ]2 o 2 ≤i≤n [α2np →α2np+1 ]0 [β2np →β2np+1 ]0 [γ2np →γ2np+1 ]2 [xi,j,2np →xi,j,2np+1 ]2 [xi,j,2np →xi,j,2np+1 ]2 [x∗ i,j,2np →x∗ i,j,2np+1 ]2    o 1 ≤i≤n, 1≤j≤p Thus, C2np+1(0) = {α2np+1, β2np+1}, and he e exis 2nmemb anes labelled by 1 con aining an objec #; and 2nmemb anes labelled by 2 con aining he inpu mul ise cod2np+1(ϕ), an objec γ2np+1,pcopies o Ti( esp. Fi) being 1 ≤i≤ni hei co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o Fi( esp. Ti) i k+ 2 ≤i≤nand objec s i,2np−i+2, k+ 2 ≤i≤n, being ∈ { , }. - Supposing, by induc ion, esul is ue o k(1 ≤k≤n−1) -C2np+k(0) = {α2np+k, β2np+k} - In C2np+k he e a e 2nmemb anes labelled by 1 such ha each o hem con ains kobjec s #. - In C2np+k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2np+k(ϕ); ?an objec γ2np+k; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni hei co esponding i ( esp. i) objec exis s in ha b anch, and 1 copy o Fi( esp. Ti) i k+ 1 ≤i≤n; and ?objec s i,2np+k−i+1,k+ 1 ≤i≤n, being ∈ { , }. Then, con igu a ion C2np+kyields con igu a ion C2np+k+1 by applying he ules: [ k+1,2np F1]2→#[ ]2 [ k+1,2np T1]2→#[ ]2 [ i,2np+k−i+1 → i,2np+k−i+2 ]2 [ i,2np+k−i+1 → i,2np+k−i+2 ]2 o 2 ≤i≤n [α2np+k→α2np+k+1 ]0 [β2np+k→β2np+k+1 ]0 [γ2np+k→γ2np+k+1 ]2 [xi,j,2np+k→xi,j,2np+k+1 ]2 [xi,j,2np+k→xi,j,2np+k+1 ]2 [x∗ i,j,2np+k→x∗ i,j,2np+k+1 ]2    o 1 ≤i≤n, 1≤j≤p P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 275 The e o e, he ollowing holds -C2np+k+1(0) = {α2np+k+1, β2np+k+1} - In C2np+k+1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains k+ 1 objec s #. - In C2np+k+1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise cod2np+k+1(ϕ); ?an objec γ2np+k+1; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni hei co esponding i ( esp. i) objec exis s in ha b anch, and 1 copy o Fi( esp. Ti) i k+ 2 ≤i≤n; and ?objec s i,2np+k−i+2,k+ 2 ≤i≤n, being ∈ { , }. - In o de o p o e (b) i is enough o no ice ha , on he one hand, om (a) con igu a ion Cn+2np−13holds: -Cn+2np−1(0) = {αn+2np−1, βn+2np−1} - In Cn+2np−1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains n−1 objec s #. - In Cn+2np−1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise codn+2np−1(ϕ); ?an objec γn+2np−1; ? p copies o Ti( esp. Fi) being 1 ≤i≤ni he co esponding i( esp. i) objec exis s in ha b anch, and 1 copy o Fn( esp. Tn); and ?an objec n,2np, being ∈ { , }. Then, con igu a ion Cn+2np−1yields con igu a ion Cn+2np by applying he ules: [ n,2np F1]2→#[ ]2 [ n,2np T1]2→#[ ]2 [αn+2np−1→αn+2np ]0 [βn+2np−1→βn+2np ]0 [γn+2np−1→γn+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [x∗ i,j,n+2np−1→x∗ i,j,n+2np ]2    o 1 ≤i≤n, 1≤j≤p The e o e, he ollowing holds -Cn+2np(0) = {αn+2np, βn+2np} - In Cn+2np he e a e 2nmemb anes labelled by 1 such ha each o hem con ains nobjec s #. - In Cn+2np he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he inpu mul ise codn+2np(ϕ); ?an objec γn+2np; and 3No e ha n+ 2np −1 = 2np + (n−1) 276 L. Valencia-Cab e a e al. ? p copies o Ti( esp. Fi) being 1 ≤i≤ni hei co esponding i( esp. i) objec exis s in ha b anch.  5.2 Fi s checking s age A his s age, we y o de e mine he clauses sa is ied o he u h assignmen encoded by each b anch. Fo ha , ules om 5.5 will be applied in such manne ha in he m- h s ep, being m=ln+k(1 ≤k≤n, 0 ≤l≤p−1), clause Cl+1 will be e alua ed wi h he k- h a iable o he o mula. This s age will ake exac ly np s eps. P oposi ion 4. Le C= (C0,C1,...,Cq)be a compu a ion o he sys em Π(s(ϕ)) wi h inpu mul ise cod(ϕ). (a)Fo each k(1≤k≤n) and l(0≤l≤p−1) a con igu a ion Cn+2np+ln+kwe ha e he ollowing: -Cn+2np+ln+k(0) ={αn+2np+ln+k, βn+2np+ln+k} - The e a e 2nmemb anes labelled by 1 such ha each o hem con ains ? m objec s cj, (1≤j≤l+ 1,0≤ ≤ln +k−1), ha is, clauses ha ha e been sa is ied by any a iable; and ? n +ln +k−mobjec s #. - The e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he (n−k)- h las elemen s o codn+2np+ln+k(ϕ)l+1 l+1; ? he inpu mul ise codn+2np+ln+k(ϕ)p l+2; ?an objec γn+2np+ln+k; and ? p−lcopies o objec s Tio Fi,k+1 ≤i≤n,p−l−1copies o he wise, co esponding o he u h assignmen assigned o he b anch. (b)Cn+3np(0) = {αn+3np, βn+3np}, and in Cn+3np he e a e 2nmemb anes labelled by 1, such ha each o hem con ains mobjec s cj, (1≤j≤p,0≤ ≤np−1), ha is, he clauses sa is ied by any a iable and n+np −mobjec s #; and 2n memb anes labelled by 2 such ha each o hem con ains an objec γn+3np. P oo . (a) is going o be demons a ed by induc ion on l - The base case l= 0 is goig o be demons a ed by induc ion on k - The base case k= 1 is i ial because: - a con igu a ion Cn+2np we ha e: Cn+2np(0) = {αn+2np, βn+2np}and he e exis 2nmemb anes labelled by 1, such ha each o hem con- ains; and 2nmemb anes labelled by 2 such ha each o hem con ains nobjec s # he inpu mul ise codn+2np(ϕ), an objec γn+2np and p copies o objec s Tiand Fi, 1 ≤i≤n, ep esen ing he co espon- den u h assignmen o he b anch. Then, con igu a ion Cn+2np yields con igu a ion Cn+2np+1 by applying he ules: P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 277 [T1x1,1,n+2np ]2−→ c1,0[ ]2 [T1x1,1,n+2np ]2−→ #[ ]2 [T1x∗ 1,1,n+2np ]2−→ #[ ]2 [F1x1,1,n+2np ]2−→ #[ ]2 [F1x1,1,n+2np ]2−→ c1,0[ ]2 [F1x∗ 1,1,n+2np ]2−→ #[ ]2 4 [αn+2np →αn+2np+1 ]0 [βn+2np →βn+2np+1 ]0 [γn+2np →γn+2np+1 ]2 [xi,j,n+2np →xi,j,n+2np+1 ]2 [xi,j,n+2np →xi,j,n+2np+1 ]2 [x∗ i,j,n+2np →x∗ i,j,n+2np+1 ]2    o 1 ≤i≤n, 1≤j≤p Thus, Cn+2np+1(0) = {αn+2np+1, βn+2np+1}, and he e exis 2nmemb anes labelled by 1 con aining nobjec s # and an objec c1,0i he co esponding u h assignmen makes ue clause 1 wi h a iable 1, ano he objec # o he wise; and 2nmemb anes labelled by 2 con aining he las n−1 elemen s o codn+2np+1(ϕ)1 1, he inpu mul ise codn+2np+1(ϕ)p 2,pcopies o Tio Fi, being 2 ≤i≤n, and p−1 copies o T1o F1. - Supposing, by induc ion, esul is ue o k(1 ≤k≤n) -Cn+2np+k(0) = {αn+2np+k, βn+2np+k} - In Cn+2np+k he e a e 2nmemb anes labelled by 1 such ha each o hem con ains ? m objec s c1, (0 ≤ ≤k−1), ha is, he numbe o a iables wi h he co esponding u h assignmen ha makes ue he inpu o mula ϕ; and ? n +k−mobjec s #. - In Cn+2np+k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ? he (n−k)- h las elemen s o codn+2np+k(ϕ)1 1; ? he inpu mul ise codn+2np+k(ϕ)p 2; ?an objec γn+2np+k; and ? p copies o objec s Tio Fi,k+ 1 ≤i≤n,p−1 copies i 1 ≤i≤k, co esponding o he u h assignmen assigned o he b anch. Then, con igu a ion Cn+2np+kyields con igu a ion Cn+2np+k+1 by ap- plying he ules: [Tkx1,1,n+2np+k]2−→ c1,0[ ]2 [Tkx1,1,n+2np+k]2−→ #[ ]2 [Tkx∗ 1,1,n+2np+k]2−→ #[ ]2 [Fkx1,1,n+2np+k]2−→ #[ ]2 [Fkx1,1,n+2np+k]2−→ c1,0[ ]2 [Fkx∗ 1,1,n+2np+k]2−→ #[ ]2 5 4I k= 1, l = 0, hen i= 1, j = 1, so 2np +n+n(j−1) + (i−1) = n+ 2np 5I l= 0, hen i=k+ 1, j = 1, so 2np + 2n+n(j−1) + (i−1) = 2n+ 2np +k 284 L. Valencia-Cab e a e al. ?an objec γn+4np o de j−1( espec i ely, an objec dk) i he co esponding u h assignmen does no make ue ( esp., makes ue) he clause C1 o Cj(2≤j≤p) ( esp., he i s kclauses); and ? mj−1objec s cj o 1≤j≤min(e j, k + 1) and mjobjec s cj o min(e j, k + 2) ≤j≤p. (a1)Fo each 2k(1≤k≤p−2) a con igu a ion Cn+4np+2kwe ha e he ollowing: -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - The e a e 2nemp y memb anes labelled by 1. - The e a e 2nemp y memb anes labelled by 2 such ha each o hem con ains ?an objec γn+4np o de j−1i he co esponding u h assignmen does no make ue he clause C1o Cj(2≤j≤p); and ? mj−1objec s cj o 1≤j≤min(e j, k)and mjobjec s cj o min(e j, k+ 1) ≤j≤p. (b)Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1 he e a e 2nmemb anes labelled by 1, such ha each o hem con ains an objec dpi and only i he co esponding u h assignmen makes ue he inpu o mula ϕ(de j−1o he wise); and 2nmemb anes labelled by 2, such ha each o hem con ains mj−1objec s cj o 1≤j≤min(e j, p+1),mjobjec s cj o min(e j, p+ 1) ≤j≤pand an objec γn+4np ( espec i ely, de j) i clause C1( esp., Cj) is no sa is ied by he co esponding u h assignmen . P oo . (a) is going o be demons a ed by induc ion on k - The base case k= 1 is i ial because: (a0) a con igu a ion Cn+4np we ha e: Cn+4np(0) = {αn+4np, βn+4np}and he e exis 2nemp y memb anes labelled by 1; and he e exis 2nmemb anes labelled by 2 con aining an objec γn+4np and mobjec s cj(1 ≤j≤p). Then, con igu a ion Cn+4np yields con igu a ion Cn+4np+1 by applying he ules: [αn+4np →αn+4np+1 ]0 [βn+4np →βn+4np+1 ]0 [γ4np+2nc1]2−→ d1[ ]2 (a1) a Cn+4np+1(0) = {αn+4np+1, βn+4np+1}and he e exis 2nmemb anes la- belled by 1 con aining an objec d1i and only i he e was a leas one objec c1wi hin memb ane labelled by 1 a con igu a ion Cn+4np; and 2n memb anes labelled by 2 con aining an objec γn+4np i and only i he e we e no objec s c1a con igu a ion Cn+4np,m1−1 ( espec i ely, m1) objec s c1i he e was any objec cjin his memb ane in he p e ious con igu a- ion ( esp., m1) and mjobjec s cj o 2 ≤j≤p. Then, he con igu a ion Cn+4np+1 yields con igu a ion Cn+4np+2 by applying he ules: [αn+4np+1 →αn+4np+2 ]0 [βn+4np+1 →βn+4np+2 ]0 d1[ ]2−→ [d1]2 Thus, Cn+4np+2(0) = {αn+4np+2, βn+4np+2}, and he e exis 2nemp y memb anes labelled by 1; and he e exis 2nmemb anes labelled by 2 P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 285 con aining an objec d1( espec i ely, γn+4np) i he co esponding u h assignmen makes ue ( esp., doesn’ make ue) clause C1,m1−1 ( esp., m1) objec s c1and mjobjec s cj o 1 ≤j≤p. Hence, he esul holds o k= 1. - Supposing, by induc ion, esul is ue o k(0 ≤k≤p−1) -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - In Cn+4np+2k he e a e 2nemp y memb anes labelled by 1. - In Cn+4np+2k he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ?an objec γn+4np o de j−1( espec i ely, an objec dk) i he co esponding u h assignmen does no make ue ( esp., makes ue) he clause C1 o Cj(2 ≤j≤p) ( esp., he i s kclauses); and ? mj−1 objec s cj o 1 ≤j≤min(e j, k + 1) and mjobjec s cj o min(e j, k + 2) ≤j≤p. Then, con igu a ion Cn+4np+2kyields con igu a ion Cn+4np+2k+1 by apply- ing he ules: [αn+4np+2k→αn+4np+2k+1 ]0 [βn+4np+2k→βn+4np+2k+1 ]0 [dkck+1 ]2−→ dk+1[ ]2 The e o e, he ollowing holds -Cn+4np+2k+1(0) = {αn+4np+2k+1, βn+4np+2k+1} - In Cn+4np+2k+1 he e a e 2nmemb anes labelled by 1 such ha each o hem con ains an objec dk+1 i and only i he co esponding u h assignmen makes ue he i s k+ 1 clauses. - In Cn+4np+2k+1 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ?an objec γn+4np o de j−1i he co esponding u h assignmen does no make ue he clause C1o Cj(2 ≤j≤p); and ? mj−1 objec s cj o 1 ≤j≤min(e j, k) and mjobjec s cj o min(e j, k + 1) ≤j≤p. Then, con igu a ion Cn+4np+2k+1 yields Cn+4np+2k+2 by applying he ules: [αn+4np+2k+1 →αn+4np+2k+2 ]0 [βn+4np+2k+1 →βn+4np+2k+2 ]0 dk+1[ ]2−→ [dk+1 ]2 The e o e, he ollowing holds -Cn+4np+2k+2(0) = {αn+4np+2k+2, βn+4np+2k+2} - In Cn+4np+2k+2 he e a e 2nemp y memb anes labelled by 1. - In Cn+4np+2k+2 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains ?an objec γn+4np o de j−1( espec i ely, an objec dk+1) i he co e- sponding u h assignmen does no make ue ( esp., makes ue) he clause C1o Cj(2 ≤j≤p) ( esp., he i s k+ 1 clauses); and 286 L. Valencia-Cab e a e al. ? mj−1 objec s cj o 1 ≤j≤min(e j, k + 2) and mjobjec s cj o min(e j, k + 3) ≤j≤p. Hence, he esul holds o k+ 1. - In o de o p o e (b) i is enough o no ice ha , on he one han, om (a) con igu a ion Cn+4np+2p−2holds: -Cn+4np+2p−2(0) = {αn+4np+2p−2, βn+4np+2p−2} - In Cn+4np+2p−2 he e a e 2nemp y memb anes labelled by 1. - In Cn+4np+2p−2 he e a e 2nmemb anes labelled by 2 such ha each o hem con ains - an objec γn+4np o de j−1( espec i ely, dp−1) i he co esponding u h assignmen does no make ue he clause C1o Cj(2 ≤j≤p−1) ( esp., makes ue clauses Cj(1 ≤j≤p−1)); and -mj−1 objec s cj o 1 ≤j≤min(e j, p −1) and mjobjec s cj o min(e j, p)≤j≤p Then, con igu a ion Cn+4np+2p−2yields con igu a ion Cn+4np+2p−1by ap- plying he ules: [αn+4np+2p−2→αn+4np+2p−1]0 [βn+4np+2p−2→βn+4np+2p−1]0 [dp−1cp]2−→ dp[ ]2 Then, we ha e Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1 he e a e 2nmemb anes labelled by 1, such ha each o hem con ains an objec dpi and only i he co esponding u h as- signmen makes ue he inpu o mula ϕ(de j−1o he wise); and 2nmem- b anes labelled by 2, such ha each o hem con ains mj−1 objec s cj o 1≤j≤min(e j, p + 1), mjobjec s cj o min(e j, p + 1) ≤j≤pand an objec γn+4np ( espec i ely, de j) i clause C1( esp., Cj) is no sa is ied by he co esponding u h assignmen .  5.4 Ou pu s age The ou pu phase s a s a con igu a ion Cn+4np+2p−1, and akes exac ly wo s eps when he e is an a i ma i e answe and h ee s eps when he e is a nega i e one. Rules om 5.7 a e de o ed o compu e his s age. -A i ma i e answe : In his case, a con igu a ion Cn+4np+2p−1, in some mem- b ane 1 he e is an objec dp. By applying he ule [ dp]1−→ dp[ ]1(a he same ime ha [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→ βn+4np+2p]0a e execu ed), an objec dpis p oduced in memb ane 0. Then by applying he ules [ α4np+n+2pdp]0−→ yes[ ]0and [ βn+4np+2p→ βn+4np+2p+1 ]0, an objec yes is eleased o en i onmen and he compu a- ion hal s. P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 287 -Nega i e answe : In his case, a con igu a ion Cn+4np+2p−1, he e a e no mem- b anes labelled by 1 ha con ains an objec dp, so he only ules execu ed a e [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→βn+4np+2p]0. Rule [βn+4np+2p→βn+4np+2p+1 ]0is execu ed in he nex s ep. Thus, a con- igu a ion Cn+4np+2p+1 in memb ane labelled by 0 we execu e ha e a copy o objec αn+4np+2pand a copy o objec βn+4np+2p+1. By applying he ule [α4np+n+2pβ4np+n+2p+1]0−→ no[ ]0an objec no is eleased o he en i on- men and hen he compu a ion hal s. 5.5 Resul Theo em 1. SAT ∈PMCDAM0(+es,mcmpou ,−d,+n). P oo . The amily Πo P sys ems p e iously cons uc ed e i ies he ollowing: (a) The amily Πis polynomially uni o m by Tu ing machines because o each n, p ∈N, he ules o Π(hn, pi) o he amily a e ecu si ely de ined om n, p ∈N, and he amoun o esou ces needed o build an elemen o he amily is o a polynomial o de in nand p, as shown below: – Size o he alphabe : 15n2p2 2+3n2p+3n2+np2+35np 2+5n+6p+6 ∈Θ(n2p2). – Ini ial numbe o memb anes: 3 ∈Θ(1). – Ini ial numbe o objec s in memb anes: 3np +n+ 3 ∈Θ(np). – Numbe o ules: 15n2p2 2+ 7n2p+np2+33np 2+ 4n+ 6p+ 4 ∈Θ(n2p2). – Maximal numbe o objec s in ol ed in any ule: 3 ∈Θ(1). (b) The amily Πis polynomially bounded wi h ega d o (SAT,cod, s): indeed o each ins ance ϕo he SAT p oblem, any compu a ion o he sys em Π(s(ϕ)) wi h inpu mul ise cod(ϕ) akes a mos 2n+ 4np + 2p+5 compu a ion s eps. (e) The amily Πis sound wi h ega d o (SAT,cod, s): indeed o each ins ance ϕo he SAT p oblem, i he compu a ion o Π(s(ϕ)) + cod(ϕ) is an accep ing compu a ion, hen ϕis sa is iable. ( ) The amily Πis comple e wi h ega d o (SAT,cod, s): indeed, o each ins ance ϕo he SAT p oblem such ha ϕis sa is iable, any compu a ion o Π(s(ϕ)) + cod(ϕ) is an accep ing compu a ion. The e o e, he amily Πo P sys ems p e iously cons uc ed sol es he SAT p ob- lem in polynomial ime and in a uni o m way. Co olla y 1. NP ∪co −NP ⊆PMCDAM0(+es,mcmpou ,−d,+n). P oo . I su ices o no ice ha SAT p oblem is a NP-comple e p ob- lem, SAT ∈PMCDAM0(+es,mcmpou ,−d,+n), and he complexi y class PMCDAM0(+es,mcmpou ,−d,+n)is closed unde polynomial- ime educ ion and un- de complemen . 288 L. Valencia-Cab e a e al. 6 Conclusions F om a compu a ional complexi y poin o iew and assuming ha P6=NP, dis- solu ion ules play a c ucial ole in classical pola iza ionless P sys ems wi h ac i e memb anes whe e he e is no coope a ion, no changing labels nei he p io i ies. In ha amewo k, PSPACE-comple e p oblems can be sol ed in polynomial ime when dissolu ion ules and di ision o elemen a y and non-elemen a y memb anes a e pe mi ed. Howe e , dissolu ion ules and di ision ules o non-elemen a y memb anes can be eplaced by minimal coope a ion ( he le -hand side o he ules has a mos wo objec s) and minimal p oduc ion ( he igh -hand side o he ules has a mos wo objec s) in objec e olu ion ules in o de o ob ain he compu a ional e iciency [11]. In his pape , he ing edien o minimal coope a ion and minimal p oduc ion in objec e olu ion ules is eplaced by minimal coope a ion and minimal p o- duc ion in send-ou communica ion ules bu we ha e need o use di ision o non-elemen a y memb anes. The new sys ems conside ed a e able o e icien ly sol e compu a ional ha d p oblems e en by conside ing simple objec e olu ion ules, ha is, hese kind o ules only p oduce one objec . An analogous esul can be ob ained i minimal coope a ion and minimal p oduc ion a e conside ed only o send-in ules, ins ead o send-ou ules ([12]). The case whe e only elemen a y di ision is allowed, while keeping he es ic- ion ha minimal coope a ion and minimal p oduc ion a e used in communica ion ules o he same di ec ion (only ou o only in) emains as u u e wo k, as well as he case whe e di ision ules a e eplaced by sepa a ion ules. Wha abou he class SAM0(+es, mcmpou ,−d, +n)? Tha is, wha hap- pens i we e isi he amewo k s udied in his pape bu eplacing di ision ules by sepa a ion ules? We can adap he easoning used in he p oo o P=PMCSAM0 bmc(−d,−n)(see [10]), and we can p o e ha by using amilies o ecognize memb ane sys ems belonging o his class, only p oblems in class P can be sol ed in polynomial ime. Acknowledgemen s This wo k was pa ially suppo ed by G an numbe s 61472328 and 61320106005 o he Na ional Na u al Science Founda ion o China. Re e ences 1. A. Alhazo , L. Pan. Pola iza ionless P sys ems wi h ac i e memb anes. G amma s, 7(2004), 141-159. 2. A. Alhazo , L. Pan, Gh. P˘aun. T ading pola iza ions o labels in P sys ems wi h ac i e memb anes. Ac a In o ma icae,41, 2-3 (2004), 111-144. P Sys ems wi h Ac i e Memb anes: Minimal Coope a ion Only Ou wa ds 289 3. T.H. Co men, C.E. Leise son, R.L. Ri es . An In oduc ion o Algo i hms. The MIT P ess, Camb idge, Massachuse s, 1994. 4. M.R. Ga ey, D.S. Johnson. Compu e s and In ac abili y A Guide o he Theo y o NP-Comple eness. W.H. F eeman and Company, 1979. 5. M.A. Gu i´e ez–Na anjo, M.J. P´e ez–Jim´enez, A. Riscos–N´u˜nez, F.J. Rome o– Campe o. On he powe o dissolu ion in P sys ems wi h ac i e memb anes. In R. F eund, Gh. P˘aun, G . Rozenbe g, A. Salomaa (eds.). Memb ane Compu ing, 6 h In e na ional Wo kshop, WMC 2005, Vienna, Aus ia, July 18-21, 2005, Re ised Selec ed and In i ed Pape s, Lec u e No es in Compu e Science,3850 (2006), 224– 240. 6. Gh. P˘aun. 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(2001), 75–90. A p elimi- na y e sion in Cen e o Disc e e Ma hema ics and Theo e ical Compu e Science Resea ch Repo s Se ies, CDMTCS-102, May 1999. 7. M.J. P´e ez-Jim´enez, A. Rome o-Jim´enez, F. Sancho-Capa ini. Complexi y classes in models o cellula compu ing wi h memb anes. Na u al Compu ing,2, 3 (2003), 265–285. 8. P. Sos´ık, A. Rod ´ıguez-Pa ´on. Memb ane compu ing and complexi y heo y: A cha - ac e iza ion o PSPACE. Jou nal o Compu e and Sys em Sciences,73 (2007), 137152. 9. L. Valencia-Cab e a, D. O ellana-Ma ´ın, M.A. Ma ´ınez-del-Amo , A. Riscos-N´u˜nez, M.J. P´e ez-Jim´enez. Pola iza ionless P sys ems wi h ac i e memb anes: Compu a- ional complexi y aspec s. Jou nal o Au oma a, Languages and Combina o ics,21, 1-2 (2016), 107123 10. L. Valencia-Cab e a, D. O ellana-Ma ´ın, A. Riscos-N´u˜nez, M.J. P´e ez-Jim´enez. Min- imal coope a ion in pola iza ionless P sys ems wi h ac i e memb anes. In C. G a- ciani, Gh. P˘aun, D. O ellana-Ma n, A. Riscos-Nez, L. Valencia-Cab e a (eds.) P o- ceedings o he Fou een h B ains o ming Week on Memb ane Compu ing, 1-5 Feb u- a y, 2016, Se illa, Spain, F´enix Edi o a, pp. 327-356. 11. L. Valencia-Cab e a, D. O ellana-Ma ´ın, M.A. Ma ´ınez-del-Amo , A. Riscos-N´u˜nez, M.J. P´e ez-Jim´enez. Reaching e iciency h ough collabo a ion in memb ane sys ems: dissolu ion, pola iza ion and coope a ion. Theo e ical Compu e Science, in p ess, 2017. 12. L. Valencia-Cab e a, D. O ellana-Ma ´ın, M.A. Ma ´ınez-del-Amo , A. Riscos-N´u˜nez, M.J. P´e ez-Jim´enez. Res ic ed pola iza ionless P sys ems wi h ac i e memb anes: minimal coope a ion only inwa ds. In his olume, 2017 (manusc ip ). 13. C. Zand on, C. Fe e i, G. Mau i. Sol ing NP-comple e p oblems using P sys ems. In I. An oniou, C.S. Calude, M.J. Dinneen (eds.) Uncon en ional Models o Compu- a ion, UMC’2K, Sp inge , London, 2000, pp. 153-164.