Cell-like and Tissue-like Memb ane
Sys ems as Recognize De ices
Miguel A. Gu i´e ez-Na anjo, Ma io J. P´e ez-Jim´enez,
Agus ´ın Riscos-N´u˜nez, and F ancisco J. Rome o-Campe o
Resea ch G oup on Na u al Compu ing
Dp . Compu e Science and A i icial In elligence, Uni e si y o Se illa, Se illa, Spain
ETS Ingenie ´ıa In o m´a ica, A da. Reina Me cedes s/n
{magu ie ,ma pe ,a iscosn, an}@us.es
Abs ac . Mos o he a ian s o memb ane sys ems ound in he li e a u e a e gene ally hough
as gene a ing de ices. In his pape ecognize compu a ional de ices (cell–like and issue–like) a e
p esen ed in he amewo k o Memb ane Compu ing, using he biological memb anes a anged hi-
e a chically, inspi ed om he s uc u e o he cell, and using he biological memb anes placed in
he nodes o a g aph, inspi ed om he cell in e –communica ion in issues. In his con ex , poly-
nomial complexi y classes o ecognize memb ane sys ems a e in oduced. The pape also add esses
he P e sus NP p oblem, and he (e icien ) sol abili y o compu a ionally ha d p oblems, in he
amewo k o hese new complexi y classes.
1 In oduc ion
One o he main goals o a compu ing model is o sol e p oblems. In o de o design compu a ional
de ices capable o a acking decision p oblems, we mus decide how o ep esen by s ings he
ins ances o he p oblem. In ha con ex , o sol e a decision p oblem consis s o ecognizing he
language associa ed wi h i .
Memb ane Compu ing is a young b anch o Na u al Compu ing p o iding dis ibu ed pa allel
compu ing models whose compu a ional de ices a e called memb ane sys ems, which a e 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.
In his a ea he e a e basically wo ways o conside compu a ional de ices: cell–like mem-
b ane sys ems and issue–like memb ane sys ems. The i s one, using he biological memb anes
a anged hie a chically, inspi ed om he s uc u e o he cell, and he second one using he bio-
logical memb anes placed in he nodes o a g aph, inspi ed om he cell in e –communica ion in
issues.
In his pape we p esen ecognize 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 ing compu a ionally ha d p oblems, cap u ing he
ue concep o algo i hm in spi e o p o iding a non–de e minis ic compu ing model.
2 P elimina ies
The compu a ional de ices o a model o compu a ion a e designed o handle inpu s and ou pu s
ha a e s ings o e a ini e alphabe .
Usually, NP-comple eness has been s udied in he amewo k o decision p oblems, bu i is
no an impo an es ic ion because one can easily ans o m any op imiza ion p oblem in o a
170 M.A. Gu i´e ez, M.J. P´e ez, A. Riscos and F.J. Rome o
oughly equi alen decision p oblem by supplying a a ge alue o he quan i y o be op imized,
and asking he ques ion whe he his alue can be a ained.
De ini ion 1. A decision p oblem is a pai (I, θ) such ha Iis a language o e a ini e alphabe
(whose elemen s a e called ins ances) and θis a o al boolean unc ion ( ha is, a p edica e) o e I.
The e exis s a na u al co espondence be ween languages and decision p oblems in he ollowing
way. Each language L, o e an alphabe Σ, has a decision p oblem, XL, associa ed wi h i as ollows:
IXL=Σ∗, and θXL={(u, 1) |u∈L}∪{(u, 0) |u∈Σ∗−L}; ecip ocally, gi en a decision p oblem
X= (IX, θX), he language LXo e he alphabe o IXco esponding o i is de ined as ollows:
LX={u∈IX|θX(u) = 1}.
The P e sus NP p oblem is he p oblem o de e mining whe he e e y p oblem sol able by
some non-de e minis ic Tu ing machine in polynomial ime can also be sol ed by some de e minis ic
Tu ing machine in polynomial ime. I is one o he ou s anding open p oblems in heo e ical
compu e science. A nega i e answe o his ques ion would con i m ha he majo i y o cu en
c yp og aphic sys ems a e secu e om a p ac ical poin o iew. A posi i e answe would no only
show he unce ain y abou he secu i y o hese sys ems, bu also his kind o answe is expec ed
o come oge he wi h a gene al p ocedu e ha p o ides a de e minis ic algo i hm sol ing mos o
he NP–comple e p oblems in polynomial ime.
In he las yea s se e al compu ing models using powe ul ools om na u e ha e been de el-
oped (because o his, hey a e known as bio-inspi ed models) and se e al solu ions in polynomial
ime o p oblems om he class NP ha e been p esen ed, making use o non-de 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.
3 Cell–like ecognize memb ane sys ems
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 ing edien s o a cell–like memb ane sys em a e he memb ane s uc u e,
he mul ise s, and he 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 conside 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 non de e minis ic and syn-
ch onous model (in he sense ha a global clock is assumed) as ollows:
•Acon 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 igu a ion o he sys em.
Cell–like and issue–like memb ane sys ems 171
•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 non–
de e minis ic, and maximally pa allel manne ( he ules a e chosen in a non–de 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.
•Acompu 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 which 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 e sion, cell–like memb ane sys ems can be seen as gene a ing de ices, wo king in
a non–de e minis ic and maximally pa allel manne , wi h ou pu memb ane, and wi hou inpu
memb ane.
Bu we a e e y in e es ed in o use cell-like memb ane sys ems in o de o sol e decision
p oblems. Wha a e he necessa y ing edien s o sol e p oblems wi h a compu a ional de ice?
We will see ha we mus wo k wi h non–de e minis ic (bu con luen ) sys ems, using maximal
pa allelism, wi hou ou pu memb ane ( he ou pu will be in he en i omen ), and wi h inpu
memb ane.
De ini ion 2. 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 labelled 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).
De ini ion 3. Acell–like ecognize memb ane sys em is a P sys em wi h inpu , (Π, Σ, iΠ), and wi h
ex e nal ou pu such ha : (1) The wo king alphabe con ains wo dis inguished elemen s YES, NO;
(2) All compu a ions hal ; and (3) In e e y compu a ion o Π, ei he some objec YES o some
objec NO (bu no bo h) mus ha e been eleased in o he en i onmen , and only in he las s ep
o he compu a ion.
We say ha Cis an accep ing ( 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 o C.
We deno e by R he class o all cell–like ecognize memb ane sys ems.
We p opose o sol e a decision p oblem h ough a amily o P sys ems (cons uc ed in a uni o m
way) such ha each elemen o he amily p ocesses all he ins ances o equi alen size, in some
sense (we say ha hese solu ions a e uni o m solu ions).
Nex , we de ine wha means o sol e a decision p oblem in he amewo k o cell–like memb ane
sys ems, and in an uni o m way.
De ini ion 4. We say ha a decision p oblem X= (IX, θX) is sol able in polynomial ime by a
amily Π= (Π(n))n∈N, o R, and we deno e his by X∈PMCR, i he ollowing is ue:
•The amily Πis polynomially uni o m by Tu ing machines; ha is, he e exis s a de e minis ic
Tu ing machine cons uc ing Π(n) om n∈Nin polynomial ime.
•The e exis s a pai (cod, s) o polynomial- ime compu able unc ions whose domain is L, such
ha :
–Fo each u∈L,s(u) is a na u al numbe and cod(u) is an inpu mul ise o Π(s(u)).
172 M.A. Gu i´e ez, M.J. P´e ez, A. Riscos and F.J. Rome o
–The amily Πis polynomially bounded wi h ega d o (X, cod, s); ha is, he e exis s a
polynomial unc ion p, such ha o each u∈IXe e y compu a ion o Π(h(u)) wi h inpu
g(u) is hal ing and, mo eo e , i pe o ms a mos p(|u|) s eps.
–The amily Πis sound, wi h ega d o (X, cod, s); ha is, o each u∈IXi is e i ied ha
i he e exis s an accep ing compu a ion o Π(h(u)) wi h inpu g(u), hen θX(u) = 1.
–The amily Πis comple e wi h ega d o (X, cod, s); ha is, o each u∈IXi is e i ied
ha i θX(u) = 1, hen e e y compu a ion o Π(h(u)) wi h inpu g(u) is an accep ing one.
In he abo e de ini ion we ha e imposed e e y P sys em Π(n) o be con luen , in he ollowing
sense: e e y compu a ion wi h he same inpu p oduces he same ou pu .
We ha e he class PMCRis closed unde polynomial– ime educ ion and complemen .
I sys ems wi hou inpu memb ane a e used, cons uc ing one speci ic sys em o each ins ance,
bu keeping he ‘polynomially uni o m by Tu ing machines’ condi ion, hen we say ha he ob ained
solu ions a e semi–uni o m. We shall deno e by PMC∗
R he class o p oblems sol able in polynomial
ime by a semi–uni o m amily o sys ems in R.
4 The P e sus NP p oblem in he con ex o cell–like
ecognize memb ane sys ems
We conside de e minis ic Tu ing machines as language ecognize de ices. Then, we can associa e
wi h each de e minis ic Tu ing machine a decision p oblem, which will pe mi 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 [12,20]).
De ini ion 5. Le Mbe a Tu ing machine wi h inpu alphabe ΣM. The decision p oblem associa ed
wi h Mis he p oblem XM= (I, θ), whe e I=Σ∗
M, and o e e y w∈Σ∗
M,θ(w) = 1 i and only i
Maccep s w.
Ob iously, he decision p oblem XMis sol able by he Tu ing machine M.
De ini ion 6. We say ha a Tu ing machine, M, is simula ed in polynomial ime by a amily o
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. Tha is, 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 wo king space 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 [22].
P oposi ion 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 ecognize memb ane sys ems using only
basic ules.
Recip ocally, in [20] he ollowing esul was p o ed:
P oposi ion 2. Fo e e y decision p oblem sol able in polynomial ime by a amily o cell–like ecog-
nize memb ane sys ems using only basic ules, he e exis s a Tu ing machine sol ing i in polynomial
ime.
Unde he hypo hesis P6=NP, Zand on e al. [23] es ablished he limi a ions o cell-like mem-
b 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. [20] ob aining he ollowing wo cha ac e iza-
ions o he P6=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 ecognize memb ane sys ems using only basic ules.
Cell–like and issue–like memb ane sys ems 173
Theo em 1. The ollowing p oposi ions a e equi alen :
1. P6=NP.
2. The e exis s an NP–comple e decision p oblem unsol able in polynomial ime by a amily cell–
like ecognize 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
ecognize memb ane sys ems using only basic ules.
Le us deno e by RB he class o cell–like ecognize memb ane sys ems using only basic ules.
F om he cons uc i e p oo gi en in [22], we deduce he ollowing esul cha ac e izing he s anda d
complexi y class P.
Theo em 2. P=PMCRB.
5 Recognize cell–like memb ane sys ems wi h ac i e
memb anes
A pa icula ly in e es ing class o cell–like memb ane sys ems a e he sys ems wi h ac i e mem-
b anes, whe e he memb ane di ision can be used in o de 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 .
De ini ion 7. A ecognize cell–like memb ane sys em wi h ac i e memb anes is a ecognize cell–
like memb ane sys em (Π, Σ, iΠ) whe e he ules o he associa ed P sys em a e o he ollowing
o ms (Hbeing he se o labels o Π):
1. [ a→ω]α
h o h∈H,α∈ {+,−,0},a∈Σ,ω∈Σ∗: An objec awi hin a memb ane labelled
wi h hand pola i y α, e ol es o a mul ise ω.
2. 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 labelled 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.
3. [ a]α1
h→b[ ]α2
h o h∈H,α1, α2∈ {+,−,0},a, b ∈Σ: An objec is sen ou om memb ane
labelled 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.
4. [ a]α
h→b o h∈H,α∈ {+,−,0},a, b ∈Σ: A memb ane labelled wi h his dissol ed in
eac ion wi h an objec . The skin is ne e dissol ed.
5. [ a]α1
h→[b]α2
h[c]α3
h o h∈H,α1, α2, α3∈ {+,−,0},a, b, c ∈Σ: An elemen a y 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.
6. [ [ ]α1
h1...[ ]α1
hk[ ]α2
hk+1 . . . [ ]α2
hm]α0
h0→[ [ ]α3
h1...[ ]α3
hk]α5
h0[[]α4
hk+1 ...[ ]α4
hm]α6
h0, o k≥1,
m > k,hi∈H o 0 ≤i≤m, and α1,...,α6∈ {+,−,0}, wi h {α1, α2}={+,−}. These a e
di ision ules o non–elemen a y memb anes. I he memb ane wi h label h0con ains o he
memb anes han hose wi h labels h1,...,hm, hen hey mus ha e neu al cha ge in o de o
make his ule applicable; hese memb anes and hei con en s a e duplica ed and placed in bo h
new copies o he memb ane h0. Besides, e e y objec in egion h0, as well as all memb anes and
objec s placed inside memb anes h1,...,hm, a e ep oduced in he new copies o memb ane h0.
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 non de e minis ic way), bu any objec
which can e ol e by one ule o any o m, mus e ol e.

174 M.A. Gu i´e ez, M.J. P´e ez, A. Riscos and F.J. Rome o
•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 labelled 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 labelled 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 ecognize 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 ecognize memb ane sys ems: Knapsack ( [14]), Subse Sum ( [13]), Pa i ion ( [4]), SAT
( [19]), Clique ( [1]), Bin Packing ( [15]), and CAP ( [16]).
Ha ing in mind ha he complexi y class PMCAM is closed unde complemen and polynomial
ime educ ions we ha e he ollowing esul .
P oposi ion 3. NP ⊆PMCAM, and co-NP ⊆PMCAM.
The complexi y class PMCAM does no seem p ecise enough o desc ibe classical complexi y classes
below NP. The e o e, i is challenging o in es iga e weake a ian s o cell–like memb ane sys ems
able o cha ac e ize classical complexi y classes.
In [2] uni e sali y has been achie ed by emo ing he pola iza ion o memb anes om P sys ems
wi h ac i e memb anes bu allowing he change o memb ane labels.
Se e al e icien solu ions o NP–comple e p oblems ha e been ob ained wi hin he ollowing
a ian o memb ane sys ems wi h ac i e memb anes:
•P sys ems using 2–di ision o elemen a y memb anes, wi hou coope a ion, wi hou p io i ies,
wi hou label changing, bu using only wo elec ical cha ges (A. Alhazo [2], A. Riscos [21]).
•P sys ems using 2–di ision o elemen a y memb anes, wi hou coope a ion, wi hou p io i ies,
wi hou label changing, wi hou pola iza ions, bu using bi–s able ca alys s (M.J. P´e ez and
F.J Rome o [17]).
•P sys ems wi hou pola iza ions, wi hou coope a ion, wi hou p io i ies, wi hou label chang-
ing, wi hou di ision, bu using h ee ypes o memb ane ules: sepa a ion, me ging and elease
(L. Pan e al. [7]).
•P sys ems wi h sepa a ion ules ins ead o di ision ules, in wo di e en cases: (a) using
pola iza ions and sepa a ion ules; and (b) wi hou pola iza ions, bu using sepa a ion ules
wi h change o memb ane labels (L. Pan and T.O. Ishdo j [8]).
I is possible o ob ain polynomial ime solu ions o NP–comple e p oblems h ough cell–like ec-
ognize memb ane sys ems wi h ac i e memb anes using 2-di ision o elemen a y memb anes. Bu ,
wha happens i we emo e pola iza ions? We deno e by AM0 he class o his kind o ecognize
P sys ems.
Ques ion: Wha is exac ly he class o decision p oblems sol able in polynomial ime by amilies
o sys ems belonging o AM0?
We deno e by AM0(α, β), whe e α∈ {−d, +d}and β∈ {−ne, +ne}, he class o all cell–
like ecognize P sys ems wi h pola iza ionless 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.
P oposi ion 4. Fo each α∈ {−d, +d}and β∈ {−ne, +ne}we ha e:
(1) PMCAM0(α,β)⊆PMC∗
AM0(α,β).
Cell–like and issue–like memb ane sys ems 175
(2) PMCAM0(α,−ne)⊆PMCAM0(α,+ne).
(3) PMC∗
AM0(α,−ne)⊆PMC∗
AM0(α,+ne).
(4) PMCAM0(−d,β)⊆PMCAM0(+d,β).
(5) PMC∗
AM0(−d,β)⊆PMC∗
AM0(+d,β).
In he amewo k o ecognize P sys ems wi h memb ane di ision bu wi hou using pola iza ions i
has been shown a su p ising ole o he dissolu ion ules, as i makes he di e ence be ween e iciency
and non–e iciency o P sys ems wi h memb ane di ision and wi hou pola iza ion ( [3,5]).
Theo em 3. We ha e he ollowing:
(1) P=PMCAM0(−d,β)=PMC∗
AM0(−d,β), o each β∈ {−ne, +ne}.
(2) NP ∪co −NP ⊆PMC∗
AM0(+d,+ne).
(3) PSPACE ⊆PMCAM0(+d,+ne).
6 Tissue–like ecognize memb ane sys ems wi h ac i e
memb anes
In his sec ion we conside compu a ional de ices inspi ed om he cell in e –communica ion in
issues, and adding he ing edien o cell di ision ules o he same o m as in cell–like memb ane
sys ems wi h ac i e memb anes, bu wi hou using pola iza ions.
In hese sys ems, he ules a e used in he non-de e minis ic maximally pa allel way, bu we
suppose ha when a cell is di ided, i s in e ac ion wi h o he cells o wi h he en i onmen is
blocked; ha is, i a di ision ule is used o di iding a cell, hen his cell does no pa icipa e in
any o he ule, o di ision o communica ion. The se o communica ion ules implici ely p o ides
he g aph associa ed wi h he sys em h ough he labels o he memb anes. The cells ob ained by
di ision ha e he same labels as he mo he cell, hence he ules o be used o e ol ing hem o
hei objec s a e inhe i ed.
De ini ion 8. A issue–like memb ane sys em wi h ac i e memb anes is a uple
Π= (Γ, Σ, M1,...,Mp, E, R, iin),
whe e:
1. p≥1 ( he ini ial deg ee o he sys em; he sys em con ains pcells, labelled wi h 1,2,...,p);
2. Γis he wo king alphabe con aining wo dis inguished objec s YES and NO;
3. Σis an (inpu ) alphabe s ic ly con ained in Γ.
4. M1,...,Mpa e mul ise s o e Γ−Σ, desc ibing he objec s placed in he cells o he sys em
(we suppose ha a leas one copy o YES and NO is in some o hese mul ise s);
5. E⊆Γis he se o objec s p esen in he en i onmen in a bi a y many copies each ( he
objec s YES and NO a e no p esen in E);
6. Ris a ini e se o de elopmen al ules, o he ollowing o ms:
(a) (i, u/ , j), o i, j ∈ {0,1,2, . . . , p}, i 6=j, and u, ∈Γ∗; 1,2,...,p iden i y he cells o he
sys em, 0 is he en i onmen : When applying a ule (i, x/y, j), he objec s o he mul ise
ep esen ed by ua e sen om egion i o egion jand simul aneously he objec s o he
mul ise a e sen om egion j o egion i;
(b) [ a]i→[b]i[c]i, whe e i∈ {1,2, . . . , p}and a, b, c ∈Γ: Unde he in luence o objec a,
he cell wi h label iis di ided in wo cells wi h he same label; in he i s copy he objec
ais eplaced by b, in he second copy he objec ais eplaced by c; all o he objec s a e
eplica ed and copies o hem a e placed in he wo new cells.
176 M.A. Gu i´e ez, M.J. P´e ez, A. Riscos and F.J. Rome o
7. iin ∈ {1, . . . , n}is he label o he inpu memb ane.
Le mbe a mul ise o e Σ. The ini ial con igu a ion o Πwi h inpu mis he uple (M1,...,Miin ∪
m, . . . , Mp).
The ules o a issue–like memb ane sys em as abo e a e used in he non-de e minis ic maxi-
mally pa allel manne as cus oma y in memb ane compu ing. In each s ep, we apply a se o ules
which is maximal (no u he ule can be added), wi h he ollowing impo an es ic ion: i a cell is
di ided, hen he di ision ule is he only one which is applied o ha cell in ha s ep, i s objec s
do no pa icipa e in any communica ion ule.
The compu a ion s a s om he ini ial con igu a ion and p oceeds as de ined abo e; only
hal ing compu a ions gi e a esul , and he esul is gi en by he p esence o a dis inguished objec
in he en i onmen .
De ini ion 9. A issue–like memb ane sys em wi h ac i e memb anes Πis a ecognize sys em i :
(a) all compu a ions hal ; and (b) in e e y compu a ion o Π, ei he a copy o he objec YES o a
copy o he objec NO (bu no bo h) is sen in o he en i onmen .
We say ha Cis an accep ing ( ejec ing) compu a ion i he objec YES ( espec i ely, he objec
NO) appea s in he en i onmen associa ed wi h he co esponding hal ing con igu a ion o C.
We deno e by T R he class o issue–like ecognize memb ane sys ems wi h ac i e memb anes.
In o de o p esen he concep o uni o m sol abili y in he amewo k o memb ane sys ems
as abo e, we de ine he concep o polynomial encoding om a language in a amily o issue–like
ecognize memb ane sys ems wi h ac i e memb anes.
De ini ion 10. Le Lbe a language, and Π= (Π(n))n∈Na amily o issue–like ecognize mem-
b ane sys ems o T R. A polynomial encoding o Lin Πis a pai (cod, s) o polynomial- ime
compu able unc ions whose domain is L, and o each u∈L,s(u) is a na u al numbe and cod(u)
is an inpu mul ise o he sys em Π(s(u)).
In he p esen pape we a e in e es ed in he compu ing e iciency. Tha is why we ha e in oduced
a a ian o issue–like sys ems wi h memb ane di ision.
Nex we de ine he concep o sol abili y in his new amewo k and in a simila way o
De ini ion 4.
De ini ion 11. We say ha a decision p oblem X= (IX, θX) is sol able in polynomial ime by a
amily Π= (Π(n))n∈N, o issue–like ecognize memb ane sys ems wi h ac i e memb anes, and
we deno e his by X∈PMCT R, i he ollowing is ue:
•The amily Πis polynomially uni o m by Tu ing machines.
•The e exis s a polynomial encoding (cod, s) om IX o Πsuch ha he amily Πis polynomially
bounded, sound and comple e wi h ega d o (X, cod, s).
We also ha e he class PMCT R is closed unde polynomial– ime educ ion and complemen .
We ha e said no hing abou he way he compu a ions p oceed; in pa icula , hey can be
non-de e minis ic, as s anda d in memb ane compu ing. I is impo an howe e o ema k ha he
sys ems always s op and hey always send ou an objec which is he co ec answe o he ins ance
o he p oblem ha hey a e p ocessing.
This na u al ex ension o issue P sys ems p o ides he possibili y o sol ing SAT in polynomial
ime, in a con luen way: a p ecise imes, one o he objec s YES, NO is sen o he en i onmen ,
gi ing he answe o he ques ion whe he he inpu p oposi ional o mula is sa is iable. We e e
o [11] o a mo e de ailed p esen a ion o he ollowing design.
Le us conside a p oposi ional o mula ϕ=C1∧ · · · ∧ Cm, consis ing o mclauses Cj=
yj,1∨ · · · ∨ yj,kj, whe e yj,i ∈ {xl,¬xl|1≤l≤n}( he e a e used n a iables). Wi hou loss o
gene ali y, we may assume ha no clause con ains wo occu ences o some xio wo occu ences
Cell–like and issue–like memb ane sys ems 177
o some ¬xi( he o mula is no edundan a he le el o clauses), o bo h xiand ¬xi(o he wise
such a clause is i ially sa is iable, hence can be emo ed).
We conside he amily Π={Π(hn, mi) : n, m ∈N}o issue–like ecognize memb ane
sys ems, being hn, mi=(n+m)·(n+m+1)
2+n.
The issue–like ecognize memb ane sys em
Π(hn, mi)=(Γ(hn, mi), Σ(hn, mi),M1,M2, E(hn, mi), R(hn, mi), iin)
will p ocess all Boolean o mulae in conjunc i e no mal o m wi h n a iables and mclauses, and
is de ined as ollows:
Γ(hn, mi) = {ai, i, i|1≤i≤n}∪{ i|1≤i≤m}
∪ {Ti,1, Fi,1|1≤i≤n} ∪ {T0
i,j , F0
i,j |1≤i≤n, 1≤j≤m+ 1}
∪ {si,j , s0
i,j |1≤i≤n, 1≤j≤m}
∪ {bi|1≤i≤3n+m+ 1}∪{ci|1≤i≤n+ 1}
∪ {di|1≤i≤3n+nm +m+ 2}∪{ei|1≤i≤3n+nm +m+ 4}
∪ { , g, Y ES, NO},
Σ(hn, mi) = {si,j , s0
i,j |1≤i≤n, 1≤j≤m},
M1=Y ES NO b1c1d1e1,
M2= ga1a2...an,
E(hn, mi) = Γ(hn, mi)− {Y ES, NO},
iin = 2,
and he ollowing ules.
1. [ ai]2→[Ti,1]2[Fi,1]2, o all i= 1,2, . . . , n.
2. (1, bi/b2
i+1,0), o all i= 1,2,...,n+ 1.
3. (1, ci/c2
i+1,0), o all i= 1,2,...,n+ 1.
4. (1, di/d2
i+1,0), o all i= 1,2,...,n+ 1.
5. (1, ei/ei+1,0), o all i= 1,2,...,3n+nm +m+ 3.
6. (1, bn+1cn+1/ , 2).
7. (1, dn+1/g, 2).
8. (2, cn+1Ti,1/cn+1T0
i,1,0).
9. (2, cn+1Fi,1/cn+1F0
i,1,0), o each i= 1,2,...,n.
10. (2, T0
i,j / iT0
i,j+1,0).
11. (2, F0
i,j / iF0
i,j+1,0), o each i= 1,2,...,n and j= 1,2,...,m.
12. (2, bi/bi+1,0).
13. (2, di/di+1,0), o all i=n+ 1, . . . , (n+ 1) + (2n+m)−1.
14. (2, b3n+m+1 isi,j /b3n+m+1 j,0).
15. (2, b3n+m+1 is0
i,j /b3n+m+1 j,0), o all 1 ≤i≤nand 1 ≤j≤m.
16. (2, di/di+1,0), o all i= 3n+m+ 1,...,(3n+m+ 1) + nm −1.
17. (2, d3n+nm+m+i i/d3n+nm+m+i+1,0), o all i= 1,2, . . . , m.
18. (2, d3n+nm+2m+1/ Y ES, 1).
19. (2, Y ES/λ, 0).
20. (1, e3n+nm+2m+2 NO/λ, 2).
21. (2, NO/λ, 0).