On the efficiency of cell-like and tissue-like recognizing membrane systems

On he E iciency o Cell-Like and Tissue-Like Recognizing Memb ane Sys ems Miguel A. Gu i´e ez-Na anjo, Ma io J. P´e ez-Jim´enez, Agus ´ın Riscos-N´u˜nez, F ancisco J. Rome o-Campe o Resea ch G oup on Na u al Compu ing, Depa men o Compu e Science and A i icial In elligence, ETS Ingenie ´ıa In o m´a ica, Uni e si y o Se illa, A da. Reina Me cedes s/n, Se illa, Spain Cell-like ecognizing memb ane sys ems a e compu a ional de ices in he amewo k o memb ane compu ing inspi ed om he s uc u e o li ing cells, whe e biological memb anes a e a anged hie a chically. In his pape issue-like ecognizing memb ane sys ems a e p esen ed. The idea is o conside ha memb anes a e placed in he nodes o a g aph, mimicking he cell in e communica ion in issues. In his con ex , polynomial complexi y classes associa ed wi h ecognizing memb ane sys ems can be de ined. We ecall he de ini ion o cell-like sys ems, and we in oduce he co esponding complexi y classes o he issue-like case. Mo eo e , in his pape wo e icien solu ions o he sa is iabili y p oblem a e analyzed and compa ed om a complexi y poin o iew. 1. INTRODUCTION Memb ane compu ing is a young b anch o na u al compu ing p o iding dis- ibu ed pa allel compu a ional de ices called memb ane sys ems, which a e inspi ed om some basic biological ea u es o li ing cells, as well as om he coope a ion o cells in issues, o gans, and o ganisms. In his a ea, he e a e basically wo ways o conside compu a ional de ices: cell- like memb ane sys ems and issue-like memb ane sys ems. The i s one uses memb anes a anged hie a chically, inspi ed om he s uc u e o he cell, and he second one uses memb anes placed in he nodes o a g aph, inspi ed om he cell in e communica ion in issues. In he pas yea s, se e al compu ing models using powe ul ools om na u e ha e been de eloped (because o his, hey a e known as bioinspi ed models) and se e al solu ions in polynomial ime o NP-comple e p oblems ha e been p esen ed, making use o nonde e minism and/o o an exponen ial amoun o space. This is he eason why a p ac ical implemen a ion o such models (in biological, elec onic, o o he media) could p o ide a signi ican ad ance in he esolu ion o compu a ionally ha d p oblems. In his pape , we p esen ecognizing memb ane sys ems (bo h cell-like and issue-like a ian s) as a amewo k o add ess ways o e icien ly sol e compu a ion- ally ha d p oblems, cap u ing he ue concep o algo i hm ins ead o p o iding a (classical) nonde e minis ic solu ion. Also, we p esen a solu ion o he sa is iabili y p oblem in bo h a ian s. The pape is s uc u ed as ollows. Fi s , in Sec ion 2, cell-like ecognizing memb ane sys ems a e de ined, oge he wi h he complexi y classes associa ed wi h hem. In his con ex , Sec ion 3 discusses he P e sus NP p oblem, and Sec ion 4 shows how memb ane di ision ules in he ac i e memb anes model allow o polynomial- ime solu ions o NP-comple e p oblems. We conclude he cell-like app oach by sol ing he sa is iabili y p oblem in a linea ime, using pola iza ion- less ac i e memb anes. Then, in Sec ion 5 we in oduce pola iza ionless issue-like ecognizing memb ane sys ems wi h ac i e memb anes (adap ing he gene al de i- ni ion o ecognizing sys ems), and we also in oduce he co esponding complexi y classes (analogously as o he cell-like case). We also p esen a quad a ic solu ion o he sa is iabili y p oblem in his amewo k. Finally, conclusions a e p esen ed in he las sec ion. 2. CELL-LIKE RECOGNIZING MEMBRANE SYSTEMS In he s uc u e and unc ioning o a cell, biological memb anes play an essen ial ole. The cell is sepa a ed om i s en i onmen by means o a skin memb ane, and i is in e nally compa men alized by means o in e nal memb anes. The main syn ac ic componen s o a cell-like memb ane sys em (also called P sys em, see Re . 1 o de ails) a e a memb ane s uc u e,mul ise s, and e olu ion ules.Amemb ane s uc u e consis s o se e al memb anes a anged in a hie - a chical s uc u e inside a main memb ane ( he skin), and delimi ing egions ( he space in-be ween a memb ane and he immedia ely inne memb anes, i any). Each memb ane iden i ies a egion inside he sys em. A memb ane s uc u e can be con- side ed as a oo ed ee. Regions de ined by a memb ane s uc u e con ain objec s co esponding o chemical subs ances p esen in he compa men s o a cell. The objec s can be desc ibed by symbols o by s ings o symbols, in such a way ha mul ise o objec s a e placed in egions o he memb ane s uc u e. The objec s can e ol e acco ding o gi en e olu ion ules, associa ed wi h he egions (hence, wi h he memb anes). The seman ics o he cell-like memb ane sys ems is de ined h ough a nonde e minis ic and synch onous model (in he sense ha a global clock is as- sumed) as ollows: A con igu a ion o a cell-like memb ane sys em consis s o a memb ane s uc u e and a amily o mul ise s o objec s associa ed wi h each egion o he s uc u e. A he beginning, he e is a con igu a ion called he ini ial con ig- u a ion o he sys em. In each ime uni , we can ans o m a gi en con igu a ion in ano he con igu a ion by applying he e olu ion ules o he objec s placed inside he egions o he con igu a ions, in a nonde e minis ic and maximally pa allel manne ( he ules a e chosen in a nonde e minis ic way, and in each egion all objec s ha can e ol e mus do i ). In his way, we ge ansi ions om one con igu a ion o he sys em o he nex one. A compu a ion o he sys em is a ( ini e o in ini e) sequence o con igu a ions such ha each one is ob ained om he p e ious one by a ansi ion, and shows how he sys em is e ol ing. A compu a ion ha eaches a con igu a ion whe e no mo e ules can be applied o he exis ing objec s is called a hal ing compu a ion. The esul o a hal ing compu a ion is usually de ined h ough he mul ise associa ed wi h a speci ic ou pu memb ane (o he en i onmen ) in he inal con igu a ion. In he basic de ini ion, cell-like memb ane sys ems can be seen as gene a i e de ices, wo king in a nonde e minis ic and maximally pa allel manne , wi h ou pu memb ane, and wi hou inpu memb ane. Howe e , as we a e in e es ed in using cell- like memb ane sys ems o sol ing decision p oblems, we can adap he de ini ion as ollows: DEFINITION 2.1. A cell-like memb ane sys em wi h ex e nal ou pu is said o be a ecognizing sys em i : (a) The wo king alphabe con ains wo dis inguished elemen s yes and no; (b) all compu a ions hal , and i Cis a compu a ion o he sys em, hen ei he some objec yes o some objec no (bu no bo h) mus ha e been eleased in o he en i onmen in he las s ep o he compu a ion. A compu a ion o a ecognizing sys em is said o be an accep ing compu a ion ( espec i ely, ejec ing compu a ion) i he objec yes ( espec i ely, no) appea s in he en i onmen associa ed wi h he co esponding hal ing con igu a ion. We wan hese kinds o sys ems (which a e nonde e minis ic de ices) o p op- e ly sol ed decision p oblems acco ding o he ue algo i hmic concep . Wi h his aim, ins ead o using classical nonde e minis ic accep ance (i is enough ha one compu a ion gi es an a i ma i e answe ), i is necessa y o equi e a condi ion o con luence; ha is, he sys em p ocessing an ins ance o he p oblem mus always gi e he same answe in all compu a ions. This idea leads us o he concep s o soundness and comple eness. 2.1. Soundness and Comple eness A amily o cell-like ecognizing P sys ems will p o ide a solu ion o a deci- sion p oblem i o each ins ance o he p oblem: (a) i he e exis s an accep ing compu a ion o he memb ane sys em p ocessing i , hen he ins ance o he p oblem has an a i ma i e answe (soundness); and (b) i he ins ance o he p oblem has an a i ma i e answe , hen any compu a ion o he sys em p ocessing ha ins ance is an accep ing compu a ion (comple eness). Nex , we o malize hese ideas in he ollowing de ini ion: DEFINITION 2.2. Le X=(IX,θ X)be a decision p oblem. Le =((w))w∈IXbe a amily o ecognizing memb ane sys ems wi hou inpu . •The amily is sound wi h ega d o Xi o each ins ance w∈IXsuch ha he e exis s an accep ing compu a ion o (w), we ha e θX(w)=1. •The amily is comple e wi h ega d o Xi o each ins ance w∈IXsuch ha θX(w)=1, we ha e e e y compu a ion o (w)is an accep ing compu a ion. These concep s can be ex ended o amilies o cell-like ecognizing memb anes wi h inpu memb ane in a na u al way, bu in his case a P sys em belonging o he amily can p ocess se e al ins ances o he p oblem, p o ided ha an app op ia e inpu is supplied o he sys em. DEFINITION 2.3. AP sys em wi h inpu is a uple (, , i), whe e. (a) is a P sys em wi h wo king alphabe , wi h pmemb anes labeled by 1,...,p, and ini ial mul ise s M1,...,Mpassocia ed wi h hem; (b) is an (inpu ) alphabe s ic ly con ained in , and he ini ial mul ise s a e o e −; and (c) iis he label o a dis inguished (inpu ) memb ane. I mis a mul ise o e , hen he ini ial con igu a ion o (, , i)wi h inpu mis (μ, M1,...,Mi∪m,...,Mp). DEFINITION 2.4. Le X=(IX,θ X)be a decision p oblem. Le =((n))n∈Nbe a amily o cell-like ecognizing P sys ems wi h inpu .Apolynomial encoding o Xin is a pai (cod, s)o polynomial ime compu able unc ions o e IXsuch ha o each ins ance w∈IX,s(w)is a na u al numbe and cod(w)is an inpu mul ise o he sys em (s(w)). DEFINITION 2.5. Le X=(IX,θ X)be a decision p oblem. Le =((n))n∈Nbe a amily o cell-like ecognizing memb ane sys ems wi h inpu .Le (cod, s)be a polynomial encoding o Xin . •The amily is sound wi h ega d o (X, cod, s)i o each ins ance w∈IXsuch ha he e exis s an accep ing compu a ion o (s(w)) wi h inpu cod(w), we ha e θX(w)=1. •The amily is comple e wi h ega d o (X, cod, s)i o each ins ance w∈IXsuch ha θX(w)=1, we ha e e e y compu a ion o (s(w)) wi h inpu cod(w)is an accep ing compu a ion. Nex , we conside di e en complexi y classes in he amewo k o cell-like ecognizing memb ane sys ems. 2.2. Polynomial Semiuni o m Solu ions The i s esul s abou sol abili y o NP-comple e p oblems in polynomial ime by memb ane sys ems we e gi en by P˘ aun,2Zand on e al.,3K ishna and Rama,4and Ob ulowicz,5in he amewo k o memb ane sys ems ha lack an inpu memb ane. Thus, he cons uc i e p oo s o such esul s design one sys em o each ins ance o he p oblem. In his con ex , le us de ine polynomial complexi y classes in cell-like ec- ognizing P sys ems wi hou inpu . To sol e a decision p oblem we need, hen, o associa e wi h each ins ance o he p oblem a sys em which decides he ins ance. DEFINITION 2.6. Le Rbe a class o cell-like ecognizing P sys ems wi hou inpu memb ane. A decision p oblem X=(IX,θ X)is sol able in polynomial ime by a amily =((w))w∈IX, o P sys ems o R, and we deno e i by X∈PMC∗ R, i he ollowing holds: •The amily is polynomially uni o m by Tu ing machines; ha is, he e exis s a de e - minis ic Tu ing machine wo king in polynomial ime which cons uc s he sys em (w) om he ins ance w∈IX. •The amily is polynomially bounded; ha is, he e exis s a polynomial unc ion p(n) such ha o each w∈IX, e e y compu a ion o (w)hal in, a mos , p(|w|)s eps. •The amily is sound and comple e wi h ega d o X. We say ha he amily is a semiuni o m solu ion o he p oblem X. As a di ec consequence o wo king wi h ecognizing memb ane sys ems we ha e hese complexi y classes a e closed unde complemen . Mo eo e , hey a e closed unde polynomial ime educ ion. 2.3. Polynomial Uni o m Solu ions Nex , we deal wi h cell-like ecognizing P sys ems wi h inpu memb ane and we p opose o sol e p oblems in an uni o m way in he ollowing sense: All ins ances o a decision p oblem ha ha e he same size (acco ding o a p e ixed polynomial ime compu able c i e ion) a e p ocessed by he same sys em, on which an app op ia e inpu is supplied. Le us o malize hese ideas in he ollowing de ini ion: DEFINITION 2.7. A decision p oblem X=(IX,θ X)is sol able in polynomial ime by a amily o cell-like ecognizing P sys ems wi h inpu =((n))n∈N, and we deno e i by X∈PMCR, i he ollowing holds: •The amily is polynomially uni o m by Tu ing machines; ha is, he e exis s a de e - minis ic Tu ing machine ha cons uc s in polynomial ime he sys em (n) om n∈N. •The e exis s a polynomial encoding (cod, s)o Xin such ha –The amily is polynomially bounded wi h ega d o (X, cod, s); ha is, he e exis s a polynomial unc ion p(n)such ha o each w∈IX, e e y compu a ion o he sys em (s(w)) wi h inpu cod(w)is hal ing and, mo eo e , i pe o ms a mos p(|w|)s eps. –The amily is sound and comple e wi h ega d (X, cod, s). These complexi y classes a e closed unde complemen . Mo eo e , hey a e closed unde polynomial ime educ ion. 3. P VERSUS NP PROBLEM IN THE CONTEXT OF CELL-LIKE RECOGNIZING MEMBRANE SYSTEMS We conside de e minis ic Tu ing machines as language ecognizing de ices. Then, we can associa e wi h each de e minis ic Tu ing machine a decision p oblem, which will allow us o de ine when such a machine is simula ed by a amily o P sys ems ( his issue was also add essed, e.g., in Re s. 6 and 7). DEFINITION 3.1. Le Mbe a Tu ing machine wi h inpu alphabe M.Thedecision p oblem associa ed wi h Mis he p oblem XM=(I,θ), whe e I=∗ M, and o e e y w∈∗ M,θ(w)=1i and only i Maccep s w. Ob iously, he decision p oblem XMis sol able by he Tu ing machine M. DEFINITION 3.2. We say ha a Tu ing machine, M, is simula ed in polynomial ime by a amily o cell-like ecognizing P sys ems o he class R,i XM∈PMCR. In cell-like memb ane sys ems, e olu ion ules, communica ion ules, and ules in ol ing dissolu ion a e called basic ules. No e ha by applying his kind o ules he size o he memb ane s uc u e does no inc ease. Hence, i is no possible o cons uc an exponen ial numbe o memb anes in polynomial ime using only basic ules in a cell-like memb ane sys em. We ecall he e a esul om Chap e 9 o Re . 8. PROPOSITION 3.1. Le Mbe a de e minis ic Tu ing machine wo king in polynomial ime. Then Mcan be simula ed in polynomial ime by a amily o cell-like ecognizing P sys ems using only basic ules. Recip ocally, in Re . 7 he ollowing esul was p o ed: PROPOSITION 3.2. Fo e e y decision p oblem sol able in polynomial ime by a amily o cell-like ecognizing P sys ems using only basic ules, he e exis s a Tu ing machine sol ing i in polynomial ime. Unde he hypo hesis P= NP, Zand on e al.3es ablished he limi a ions o cell-like memb ane sys ems, which use only basic ules conce ning he e icien solu ion o NP-comple e p oblems. This esul was gene alized by P´ e ez-Jim´ enez e al.7ob aining he ollowing wo cha ac e iza ions o he P= NP ela ion by means o unsol abili y esul s in polynomial ime o NP-comple e p oblems by amilies o cell-like ecognizing memb ane sys ems using only basic ules. THEOREM 3.1. The ollowing asse ions a e equi alen : 1. P= NP. 2. The e exis s an NP-comple e decision p oblem unsol able in polynomial ime by a amily cell-like ecognizing memb ane sys ems using only basic ules. 3. Each NP-comple e decision p oblem is unsol able in polynomial ime by a amily o cell-like ecognizing memb ane sys ems using only basic ules. Le us deno e by RB he class o cell-like ecognizing memb ane sys ems using only basic ules. In Re . 9 he complexi y class Phas been cha ac e ized in e ms o cell-like ecognizing P sys ems, by p o ing he ollowing heo em. THEOREM 3.2. P=PMCRB. 4. RECOGNIZING CELL-LIKE P SYSTEMS WITH ACTIVE MEMBRANES A pa icula ly in e es ing class o cell-like memb ane sys ems is he sys ems wi h ac i e memb anes, whe e he memb ane di ision can be used o sol e compu- a ionally ha d p oblems, e.g., NP-comple e p oblems, in polynomial o e en linea ime, by a space- ime ade-o . DEFINITION 4.1. A ecognizing cell-like P sys em (, , i)is called wi h ac i e memb anes, i he ules o a e o he ollowing o ms (being he wo king alphabe , and H he se o labels o ): (a) [ a→ω]α h o h∈H,α∈{+,−,0},a∈,ω∈∗: An objec awi hin a memb ane labeled wi h hand pola i y αe ol es o a mul ise ω. (b) a[] α1 h→[b]α2 h o h∈H,α1,α 2∈{+,−,0},a,b ∈: An objec om he egion immedia ely ou side a memb ane labeled wi h his in oduced in his memb ane, possibly ans o med in o ano he objec , and simul aneously, he pola i y o he memb ane can be changed. (c) [ a]α1 h→b[] α2 h o h∈H,α1,α 2∈{+,−,0},a,b ∈: An objec is sen ou om memb ane labeled wi h h o he egion immedia ely ou side, possibly ans o med in o ano he objec , and simul aneously, he pola i y o he memb ane can be changed. (d) [ a]α h→b o h∈H,α∈{+,−,0},a,b ∈: A memb ane labeled wi h his dissol ed in eac ion wi h an objec . The skin is ne e dissol ed. (e) [ a]α1 h→[b]α2 h[c]α3 h o h∈H,α1,α 2,α 3∈{+,−,0},a,b,c ∈: A memb ane can be di ided in o wo memb anes wi h he same label, possibly ans o ming some objec s and hei pola i ies. These ules a e applied acco ding o he ollowing p inciples: •All he ules a e applied in pa allel and in a maximal manne . In one s ep, one objec o a memb ane can be used by only one ule (chosen in a nonde e minis ic way), bu any objec which can e ol e by one ule o any o m, mus e ol e. •I a memb ane is dissol ed, i s con en (mul ise and in e nal memb anes) is le ee in he su ounding egion. •I a he same ime a memb ane labeled by his di ided by a ule o ype (e) and he e a e objec s in his memb ane which e ol e by means o ules o ype (a), hen we suppose ha i s he e olu ion ules o ype (a) a e used, and hen he di ision is p oduced. O cou se, his p ocess akes only one s ep. •The ules associa ed wi h memb anes labeled by ha e used o all copies o his memb ane. A one s ep, a memb ane can be he subjec o only one ule o ypes (b)–(e). Le us deno e by AM he class o ecognizing P sys ems wi h ac i e memb anes using 2-di ision. Di e en polynomial ime solu ions o NP-comple e p oblems ha e been ob ained using his class o cell-like ecognizing memb ane sys ems: Knapsack,10 SAT,11 Clique,12 and Bin Packing.13 Hence, he ollowing p oposi ion holds: PROPOSITION 4.1. NP ⊆PMCAM, and co-NP ⊆PMCAM. Mo eo e , Sos´ ık14 p o ed ha PSPACE ⊆PMC∗ AM0(+d,+ne), whe e AM0(+d,+ne) is he class o ecognizing P sys ems wi h ac i e memb anes al- lowing di ision o nonelemen a y memb anes. The e o e, he complexi y class PMCAM does no seem p ecise enough o desc ibe classical complexi y classes below NP. Consequen ly, i is challenging o in es iga e weake models o cell-like memb ane sys ems able o cha ac e ize classical complexi y classes. Following his line, se e al e icien solu ions o NP-comple e p oblems ha e been ob ained wi hin he ollowing a ian s o cell-like P sys ems wi h ac i e memb anes: •P sys ems wi h ac i e memb anes bu using only wo elec ical cha ges (Alhazo ,15 Riscos16; •P sys ems wi h ac i e memb anes wi hou pola iza ions, bu using bis able ca alys s (P´ e ez and Rome o17); •P sys ems wi hou pola iza ions, wi hou coope a ion, wi hou p io i ies, wi hou label changing, wi hou di ision, bu using h ee ypes o memb ane ules: sepa a ion, me ging, and elease (Pan e al.18); •P sys ems wi h sepa a ion ules ins ead o di ision ules, in wo di e en cases: in he i s , using pola iza ions and sepa a ion ules; and in he second one, wi hou pola iza ions bu using sepa a ion ules ha can change memb ane labels (Pan and Ishdo j19). We can de ine pola iza ionless cell-like P sys ems wi h ac i e memb anes in a simila manne by emo ing elec ical cha ges, ha is, conside ing only ules o he ollowing ypes: (a) [ a→u]h o h∈H,a∈,u∈∗. (b) a[] h→[b]h o h∈H,a,b ∈. (c) [ a]h→b[] h o h∈H,a,b ∈. (d) [ a]h→b o h∈H,a, b ∈. (e) [ a]h→[b]h[c]h o h∈H,a, b,c ∈. We deno e by AM0 he class o pola iza ionless cell-like ecognizing P sys ems wi h ac i e memb anes. A he beginning o 2005, P˘ aun (p oblem F om Re . 20) w o e: “My a o i e ques ion ( ela ed o complexi y aspec s in P sys ems wi h ac i e memb anes and wi h elec ical cha ges) is ha abou he numbe o pola iza ions. Can he pola iza ions be comple ely a oided? The eeling is ha his is no possible—and such a esul would be a he sound: passing om no pola iza ion o wo pola iza ions amoun s o passing om non-e iciency o e iciency.” Tha is, o mally we can o mula e he so-called P˘ aun’s conjec u e as ollows: “The class o decision p oblems sol able in polynomial ime by amilies o cell-like ecognizing P sys ems belonging o AM0is he s anda d complexi y class P.” We deno e by AM0(α, β), whe e α∈{−d,+d}and β∈{−ne, +ne}, he class o all pola iza ionless cell-like ecognizing P sys ems wi h ac i e memb anes such ha (a) i α=+d( esp. α=−d) hen dissolu ion ules a e pe mi ed ( esp. o bidden); and (b) i β=+ne ( esp. β=−ne) hen di ision ules o elemen- a y and non-elemen a y ( esp. only di ision ules o elemen a y) memb anes a e pe mi ed. In he amewo k o pola iza ionless cell-like ecognizing P sys ems wi h ac i e memb anes, i u ns ou ha dissolu ion ules play a su p ising ole, as hey make he di e ence be ween e iciency and none iciency. Mo e p ecisely, he ollowing esul is p esen ed in Re . 21: THEOREM 4.1. We ha e he ollowing: (1) P=PMCAM0(−d,β)=PMC∗ AM0(−d,β), o each β∈{−ne, +ne}. (2) NP ∪co −NP ⊆PMC∗ AM0(+d,+ne). Tha is, P˘ aun’s conjec u e has a nega i e answe i dissolu ion ules a e allowed (assuming ha P= NP), and an a i ma i e answe o he wise. The inclusion shown in (2) was imp o ed in Re . 22, whe e PSPACE ⊆ PMCAM0(+d,+ne)is p o ed. The inclusion ela ions be ween complexi y classes can be summa ized g aph- ically in Figu e 1. 4.1. Sol ing he SAT P oblem by Using Pola iza ionless Cell-Like P Sys ems wi h Ac i e Memb anes The i s e icien semiuni o m solu ion o SAT (sa is iabili y p oblem) was gi en by P˘ aun,2using di ision o nonelemen a y memb anes. This esul was imp o ed by P˘ aun e al. in Re . 23 using only di ision o elemen a y memb anes (in ha pape a semiuni o m solu ion o he Hamil onian pa h p oblem using memb ane c ea ion is also p esen ed). In his sec ion, we p esen a semiuni o m solu ion o he SAT p oblem in linea ime by using pola iza ionless cell-like ecognizing P sys ems wi h ac i e memb anes. THEOREM 4.2. The sa is iabili y o any p oposi ional o mula in he conjunc i e no mal o m, using n a iables and mclauses, can be decided in a linea ime wi h espec o nby a pola iza ionless cell-like ecognizing P sys em wi h ac i e memb anes, cons uc ed in linea ime wi h espec o nand m. 5.1.1. An O e iew o he Compu a ions Memb ane 2 is epea edly di ided, each ime expanding one objec ai, co e- sponding o a a iable xi, in o Ti,1and Fi,1, co esponding o he alues ue and alse which his a iable may assume. In his way, in ns eps, we ge 2ncells wi h label 2, each one con aining one o he 2npossible u h assignmen s o he n a iables. The objec s , g a e duplica ed, hence a copy o each o hem will appea in each cell. In pa allel wi h he ope a ion o di iding cell 2, he coun e s bi,c i,d i,e i om cell 1 g ow hei subsc ip s. In each s ep, he numbe o copies o objec s o he i s h ee ypes is doubled, hence a e ns eps we ge 2ncopies o bn+1,c n+1, and dn+1. Objec s biwill check which clauses a e sa is ied by a gi en u h assignmen , objec s cia e used o mul iply he numbe o copies o i, ias we will see immedia ely, di a e used o check whe he he e is a leas one u h assignmen which sa is ies all clauses, and i such an assignmen does no exis , hen eiwill be used in o de o p oduce he objec no a he end o he compu a ion. In s ep n+1, he coun e s bn+1,c n+1,d n+1a e b ough in cells wi h label 2, in exchange o and g. Because we ha e 2ncopies o each objec o hese ypes and 2ncells 2, each one con aining exac ly one copy o and one o g, due o he maximal pa allel use o he ules, each cell 2 ge s p ecisely one copy o each o bn+1,c n+1,d n+1. No e ha cells 2 canno di ide anymo e, because he objec s ai we e exhaus ed. In he p esence o cn+1, he objec s Ti,1,F i,1ge p imed, which ini ia es he possibili y o in oducing mcopies o each iand iin each cell 2. As we ha e m clauses, hen o check hei alues o a gi en u h assignmen , we need o each clause one se o objec s encoding he alues o all a iables. No e ha his phase needs 2ns eps o p iming he objec s Ti,1,F i,1— o each objec we need one s ep, because we ha e only one copy o cn+1a ailable— hen m u he s eps o each T i,1,F i,1; all hese s eps a e done in pa allel, bu o he las p imed Ti,1,F i,1we ha e o con inue ms eps a e he 2nnecessa y o p iming. Thus, he o al numbe o s eps pe o med in his p ocess is 2n+m. In pa allel wi h he p e ious ope a ions, he coun e s biand diinc ease hei subsc ip s, un il eaching he alue 3n+m+1. This is done in all cells 2 a he same ime. Simul aneously, eiinc eases i s subsc ip in cell 1. In he p esence o b3n+m+1—and no be o e—we check he alues assumed by clauses o he u h assignmen s om each cell 2. We ha e only one copy o b3n+m+1in each cell, hence we need a mos nm s eps o his: each clause con ains a mos nli e als, and we ha e mclauses. In pa allel, dinc eases he subsc ip , un il eaching he alue 3n+nm +m+1. In each cell wi h label 2 we check whe he o no all clauses a e sa is ied by he co esponding u h assignmen . Fo each clause which is sa is ied, we inc ease by one he subsc ip o d, hence he subsc ip eaches he alue 3n+nm +2m+1 i and only i all clauses a e sa is ied. I one o he u h assignmen s om a cell 2 has sa is ied all clauses, hen we each d3n+nm+2m+1, which is sen o cell 1 in exchange o he objec s yes and . In he nex s ep, he objec yes lea es he sys em, signaling he ac ha he o mula is sa is iable. In cell 1, he coun e ewill inc ease one mo e s ep i s subsc ip , bu a e ha i will emain unchanged—i can lea e cell 1 only in he p esence o , bu his objec was al eady mo ed o cell 2. I he coun e e eaches he subsc ip 3n+nm +2m+2 and he objec is s ill in cell 1, hen he objec no can be mo ed o a cell 2, andomly chosen, and om he e i exi s he sys em, signaling ha he o mula is no sa is iable. Nex , we jus i y ha he solu ion p o ided is an uni o m solu ion. We conside he polynomial encoding (cod, s)o ISAT in , de ined as ollows: I he o mula ϕis an ins ance o SAT wi h size pa ame e s n(numbe o a iables) and m(numbe o clauses), hen s(ϕ)=n, mand cod(ϕ) is he se  1≤i≤n,1≤j≤m,1≤ ≤kj {si,j |yj, =xi}∪{s i,j |yj, =¬xi,} Tha is, in he mul ise cod(ϕ) we eplace each a iable xi om each clause Cjwi h si,j and each nega ed a iable ¬xi om each clause Cjwi h s i,j , hen we emo e all pa en heses and connec i es. In his way we pass om ϕ o cod(ϕ) in a numbe o s eps which is linea wi h espec o n·m. The p esen ed amily o issue-like ecognizing memb ane sys ems is polyno- mially uni o m by Tu ing machines, because he de ini ion o he amily is done in a ecu si e manne om a gi en ins ance o SAT, in pa icula om he cons an s n (numbe o a iables) and m(numbe o clauses). Fu he mo e he issue P sys em (n, m) uses an alphabe o 5nm +17n+4m+12 objec s, 2 ini ial cells con ain- ing n+8 objec s in all, and n ules. The leng h o any ule is bounded by 3. Clea ly, all compu a ions hal , and he numbe o s eps is bounded by 3n+nm +2m+4 (when he answe is nega i e; i he answe is a i ma i e, hen he numbe o s eps is 3n+nm +2m+2). F om he abo e we deduce he ollowing esul s: THEOREM 5.2. 1. SAT ∈PMCTR . 2. NP ⊆PMCTR ,andNP ∪co −NP ⊆PMCTR . Rema ks. We ha e p esen ed wo solu ions o he SAT p oblem by using pola iza- ionless ecognizing memb ane sys ems wi h ac i e memb anes. The i s one, in he cell-like amewo k is semiuni o m, does no use coope a ion (i.e., he le -hand sides o he ules only ha e one objec ), and i is linea in ime and in ( he ini ial) space. The second one, in he issue-like amewo k is a uni o m solu ion, uses coop- e a ion, and i is quad a ic in ime and in ( he ini ial) space. Bo h solu ions cons uc an exponen ial wo king space (in e ms o memb anes o cells) in linea ime. 6. CONCLUSIONS In his pape , we ha e p esen ed cell-like (inspi ed om he s uc u e o he cell) and issue-like (inspi ed om he cell in e -communica ion in issues) ecognizing memb ane sys ems as compu a ional de ices specially sui able o a ack he e icien sol abili y o compu a ionally ha d p oblems. In ha new amewo k, wo cha ac e iza ions o he ela ion P=NP ha e been desc ibed h ough he sol abili y o NP-comple e p oblems by a amily o cell-like ecognizing memb ane sys ems using only basic ules. The main con ibu ion o his pape is o o malize he concep o issue- like memb ane sys ems, and o p esen , in he amewo k o issue-like ecognizing memb ane sys ems, a o mal de ini ion o he polynomial complexi y class PMCTR . Besides, wo polynomial ime solu ions o he sa is iabili y p oblem by using po- la iza ionless (cell-like and issue-like) ecognizing memb ane sys ems wi h ac i e memb anes a e p esen ed. Finally, we would like o men ion wo open ques ions o u u e esea ch. Wha happens i in issue-like P sys ems di ision ules a e o bidden? Wha i communica ion ules a e es ic ed o (i, a/b, j), whe e i, j a e labels and a,b a e objec s (ins ead o mul ise s)? Acknowledgmen s The au ho s acknowledge he suppo o he p ojec TIN2005-09345-C04-01 o he Minis e- io de Educaci´ on y Ciencia o Spain, co inanced by FEDER unds and o he p ojec o Excellence TIC 581 o he Jun a de Andaluc´ ıa. Re e ences 1. P˘ aun Gh. Memb ane compu ing. An in oduc ion. Be lin: Sp inge -Ve lag; 2002. 2. P˘ aun Gh. P sys ems wi h ac i e memb anes: a acking NP–comple e p oblems. J Au oma a, Lang Comb 2001;6(1):75–90. 3. 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 CS, Dinneen MJ, edi o s. Uncon en ional models o compu a ion, UMC’2K, Be lin: Sp inge -Ve lag; 2000. pp 289–301. 4. K ishna SN, Rama R. A a ian o P sys ems wi h ac i e memb anes: sol ing NP–comple e p oblems. Romanian J In o m Sci Technol 1999;2(4):357–367. 5. Ob ulowicz A. De e minis ic P sys ems o sol ing SAT p oblem. Romanian J In o m Sci Technol 2001;4(1–2):551–558. 6. P´ e ez–Jim´ enez MJ. An app oach o compu a ional complexi y in Memb ane Com- pu ing. In: Mau i G, P˘ aun, Gh, P´ e ez–Jim´ enez MJ, Rozenbe g G , Salomaa A, edi o s. Memb ane Compu ing, 5 h In e na ional Wo kshop, WMC5, Lec u e No es in Com- pu e Science, Vol. 3365. Be lin: Sp inge ; 2005. pp 85–109. 7. P´ e ez–Jim´ enez MJ, Rome o–Jim´ enez A, Sancho–Capa ini F. The P e sus NP p oblem h ough cellula compu ing wi h memb anes. In: Jonoska N., P˘ aun Gh, Rozenbe g G, edi o s. Aspec s o molecula compu ing. Lec u e No es in Compu e Science, Vol 2950. Be lin: Sp inge ; 2004. pp 338–352. 8. Rome o–Jim´ enez A. Complexi y and uni e sali y in cellula compu ing models. PhD. Thesis, Uni e si y o Se ille, Spain, 2003. 9. Gu i´ e ez–Na anjo MA, P´ e ez–Jim´ enez MJ, Riscos–N´ u˜ nez A, Rome o–Campe o FJ, Rome o–Jim´ enez A. Cha ac e izing ac abili y by cell-like memb ane sys ems. In: K.G. Sub amanian, K. Ranga ajan, M. Mukund, edi o s. Fo mal models, languages and applica- ions. MPAI Se ies, Vol 66. Singapo e: Wo ld Scien i ic; 2006. pp 137–154. 10. P´ e ez–Jim´ enez MJ, Riscos–N´ u˜ nez A. A linea - ime solu ion o he knapsack p oblem using P sys ems wi h ac i e memb anes. In: Ma ´ ın-Vide C, P˘ aun Gh, Rozenbe g G, Salomaa A, edi o s. Memb ane compu ing, Lec u e No es in Compu e Science, Vol 2933. Be lin: Sp inge ; 2004. pp. 248–266. 11. P´ e ez–Jim´ enez MJ, Rome o–Jim´ enez A, Sancho–Capa ini F. Complexi y classes in cellula compu ing wi h memb anes. Na Compu 2003;2(3):265–285. 12. Alhazo A, Ma ´ ın–Vide C, Pan L. Sol ing g aph p oblems by P sys ems wi h es ic ed elemen a y ac i e memb anes. In: Jonoska N, P˘ aun Gh, Rozenbe g G, edi o s. Aspec s o molecula compu ing, Lec u e No es in Compu e Science, Vol 2950. Be lin: Sp inge ; 2004. pp 1–22. 13. P´ e ez–Jim´ enez MJ, Rome o–Campe o FJ. An e icien amily o P sys ems o packing i ems in o bins. J Uni e sal Compu Sci 2004; 10(5):650–670. 14. Sosik P. The compu a ional powe o cell di ision in P sys ems: Bea ing down pa allel compu e s? Na Compu 2003;2(3):287–298. 15. Alhazo A, Pan L, P˘ aun Gh. T ading pola iza ions o labels in P sys ems wi h ac i e memb anes. Ac a In o m 2004;41(2–3):111–144. 16. Riscos–N´ u˜ nez A. Cellula p og amming: e icien esolu ion o NP–comple e nume ical p oblems. Ph.D. Thesis, Uni e si y o Se ille, Spain; 2004. 17. P´ e ez–Jim´ enez MJ, Rome o–Campe o FJ. T ading pola iza ions o bi-s able ca alys s in P sys ems wi h ac i e memb anes. In: Mau i G, P˘ aun Gh, P´ e ez–Jim´ enez MJ, Rozenbe g G , Salomaa A, edi o s. Memb ane Compu ing, 5 h In e na ional Wo kshop, WMC5, Lec u e No es in Compu e Science, Vol. 3365. Be lin: Sp inge ; 2005. pp. 373–388. 18. Pan L, Alhazo A, Ishdo j T-O. Fu he ema ks on P sys ems wi h ac i e memb anes, sepa a ion, me ging, and elease ules. So Comp—A Fusion Found Me hodol Appl 2005;9(9):686–690. 19. Pan L, Ishdo j T-O. P Sys ems wi h ac i e memb anes and sepa a ion ules. J Uni e sal Compu Sci 2004;10(5):630–649. 20. P˘ aun Gh. Fu he wen y six open p oblems in memb ane compu ing. In: Gu i´ e ez-Na anjo MA, Riscos-N´ u˜ nez A, Rome o-Campe o FJ, Sbu lan D, edi o s. P oceedings o he Thi d B ains o ming Week on Memb ane Compu ing; 2005. pp 249–262. 21. Gu i´ e ez–Na anjo MA, P´ e ez–Jim´ enez MJ, Riscos–N´ u˜ nez A, Rome o–Campe o FJ. On he powe o dissolu ion in P sys ems wi h ac i e memb anes. In: Lec u e No es in Compu e Science. Be lin: Sp inge ; Vol. 3850. 2006; pp 224–240. 22. Alhazo A, P´ e ez-Jim´ enez MJ. Uni o m solu ion o QSAT using pola iza ionless ac i e memb anes. In: Du and-Lose J and Ma gens e n M, edi o s. Machines, Compu a ions, and Uni e sali y, Lec u e No es in Compu e Science, Vol. 4664. Be lin: Sp inge ; 2007. pp 122– 133. 23. P˘ aun Gh, Suzuki Y, Tanaka H, Yokomo i T. On he powe o memb ane di ision in P sys ems. Theo Compu Sci 2004;324(1):61–85.